The DOI matches its Crossref record; 68 of the 68 references it cites were found in a registry or an index.
Steiner tree problems
Abstract
We give a survey up to 1989 on the Steiner tree problems which include the four important cases of euclidean, rectilinear, graphic, phylogenetic and some of their generalizations. We also provide a rather comprehensive and up‐to‐date bibliography which covers more than three hundred items.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Reducibility among Combinatorial Problems
Karp, R. M. (1972) · Complexity of Computer Computations · doi:10.1007/978-1-4684-2001-2_9 · Cited by 11,511
Toward Defining the Course of Evolution: Minimum Change for a Specific Tree Topology
Fitch, W. M. (1971) · Systematic Biology · doi:10.1093/sysbio/20.4.406 · Cited by 6,492
Toward Defining the Course of Evolution: Minimum Change for a Specific Tree Topology
Fitch, W. M. (1971) · Systematic Zoology · doi:10.2307/2412116 · Cited by 5,635
Combinatorial optimization: networks and matroids
Lawler, E. L. (2021) · Cited by 3,359
Routing of multipoint connections
Waxman, B. M. (1988) · IEEE Journal on Selected Areas in Communications · doi:10.1109/49.12889 · Cited by 2,885
Phylogenetic analysis: models and estimation procedures
(2018) · Phylogenetic Inference, Selection Theory, and History of Science · doi:10.1017/9781316276259.010 · Cited by 2,260
PHYLOGENIES FROM MOLECULAR SEQUENCES: INFERENCE AND RELIABILITY
Felsenstein, J. (1988) · Annual Review of Genetics · doi:10.1146/annurev.ge.22.120188.002513 · Cited by 2,128
Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison
Sankoff, D., & Kruskal, J. B. (1983) · Medical Entomology and Zoology · Cited by 1,915
Methods for Computing Wagner Trees
Farris, J. S. (1970) · Systematic Biology · doi:10.1093/sysbio/19.1.83 · Cited by 1,222
A fast algorithm for Steiner trees
Kou, L., Markowsky, G., & Berman, L. (1981) · Acta Informatica · doi:10.1007/bf00288961 · Cited by 1,188
The Rectilinear Steiner Tree Problem is $NP$-Complete
Garey, M. R., & Johnson, D. S. (1977) · SIAM Journal on Applied Mathematics · doi:10.1137/0132071 · Cited by 1,124
Shamos, M. I., & Hoey, D. (1975) · 16th Annual Symposium on Foundations of Computer Science (sfcs 1975) · doi:10.1109/sfcs.1975.8 · Cited by 1,057
The shortest path through many points
Beardwood, J., Halton, J. H., & Hammersley, J. M. (1959) · Mathematical Proceedings of the Cambridge Philosophical Society · doi:10.1017/s0305004100034095 · Cited by 937
Methods for Computing Wagner Trees
Farris, J. S. (1970) · Systematic Zoology · doi:10.2307/2412028 · Cited by 918
An approximate solution for the Steiner problem in graphs
Takahashi, H., & Matsuyama, A. (1980) · Mathematica japonica · Cited by 878
A METHOD FOR DEDUCING BRANCHING SEQUENCES IN PHYLOGENY
Camin, J. H., & Sokal, R. R. (1965) · Evolution · doi:10.1111/j.1558-5646.1965.tb01722.x · Cited by 808
The NP-completeness column: An ongoing guide
Johnson, D. S. (1986) · Journal of Algorithms · doi:10.1016/0196-6774(86)90020-9 · Cited by 794
What Is Mathematics?: An Elementary Approach To Ideas And Methods
Courant, R., & Robbins, H. (1996) · doi:10.1093/oso/9780195105193.001.0001 · Cited by 777
Dreyfus, S. E., & Wagner, R. A. (1971) · Networks · doi:10.1002/net.3230010302 · Cited by 696
Convergence of an annealing algorithm
Lundy, M., & Mees, A. (1986) · Mathematical Programming · doi:10.1007/bf01582166 · Cited by 693
Gilbert, E. N., & Pollak, H. O. (1968) · SIAM Journal on Applied Mathematics · doi:10.1137/0116001 · Cited by 690
Numerical Methods for Inferring Evolutionary Trees
Felsenstein, J. (1982) · The Quarterly Review of Biology · doi:10.1086/412935 · Cited by 636
On Steiner’s Problem with Rectilinear Distance
Hanan, M. (1966) · SIAM Journal on Applied Mathematics · doi:10.1137/0114025 · Cited by 623
Steiner problem in networks: A survey
Winter, P. (1987) · Networks · doi:10.1002/net.3230170203 · Cited by 599
The Complexity of Computing Steiner Minimal Trees
Garey, M. R., Graham, R. L., & Johnson, D. S. (1977) · SIAM Journal on Applied Mathematics · doi:10.1137/0132072 · Cited by 576
Minimal Mutation Trees of Sequences
Sankoff, D. (1975) · SIAM Journal on Applied Mathematics · doi:10.1137/0128004 · Cited by 575
Steiner problem in networks: a survey
WinterP. (1987) · Networks · doi:10.5555/34233.34235 · Cited by 563
Branch and bound algorithms to determine minimal evolutionary trees
Hendy, M. D., & Penny, D. (1982) · Mathematical Biosciences · doi:10.1016/0025-5564(82)90027-x · Cited by 531
Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
Karp, R. M. (1977) · Mathematics of Operations Research · doi:10.1287/moor.2.3.209 · Cited by 439
Brooks, S. A., Yan, W., Jackson, A. K., & Deren, C. W. (2008) · Theoretical and Applied Genetics · doi:10.1007/s00122-008-0801-8 · Cited by 436
Algorithms and Complexity: New Directions and Recent Results
Traub, J. F. (1976) · UCLA - Biblioteca de Ciencias y Tecnologia Felix Morales Bueno · Cited by 427
On Steiner Minimal Trees with Rectilinear Distance
Hwang, F. K. (1976) · SIAM Journal on Applied Mathematics · doi:10.1137/0130013 · Cited by 424
Self-citationA faster approximation algorithm for the Steiner problem in graphs
Mehlhorn, K. (1988) · Information Processing Letters · doi:10.1016/0020-0190(88)90066-x · Cited by 420
A dual ascent approach for steiner tree problems on a directed graph
Wong, R. T. (1984) · Mathematical Programming · doi:10.1007/bf02612335 · Cited by 360
Induction and Analogy in Mathematics
Pólya, G. (1954) · Medical Entomology and Zoology · Cited by 358
On the Problem of Discovering the Most Parsimonious Tree
Fitch, W. M. (1977) · The American Naturalist · doi:10.1086/283157 · Cited by 357
Gray, M. W., Sankoff, D., & Cedergren, R. J. (1984) · Nucleic Acids Research · doi:10.1093/nar/12.14.5837 · Cited by 351
Steiner's problem in graphs and its implications
Hakimi, S. L. (1971) · Networks · doi:10.1002/net.3230010203 · Cited by 347
Melzak, Z. A. (1961) · Canadian Mathematical Bulletin · doi:10.4153/cmb-1961-016-2 · Cited by 281
Minimum Mutation Fits to a Given Tree
Hartigan, J. A. (1973) · Biometrics · doi:10.2307/2529676 · Cited by 271
Locating the vertices of a steiner tree in an arbitrary metric space
Sankoff, D., & Rousseau, P. (1975) · Mathematical Programming · doi:10.1007/bf01681346 · Cited by 247
The NP-completeness column: an ongoing guide
Johnson, D. S. (1985) · Journal of Algorithms · doi:10.1016/0196-6774(85)90012-4 · Cited by 243
Computational Complexity of Inferring Phylogenies by Compatibility
Day, W. H., & Sankoff, D. (1986) · Systematic Biology · doi:10.1093/sysbio/35.2.224 · Cited by 141
The rectilinear steiner arborescence problem
Rao, S. K., Sadayappan, P., Hwang, F. K., & Shor, P. W. (1992) · Algorithmica · doi:10.1007/bf01758762 · Cited by 139
Self-citationFrequency of insertion-deletion, transversion, and transition in the evolution of 5S ribosomal RNA
Sankoff, D., Cedergren, R., & Lapalme, G. (1976) · Journal of Molecular Evolution · doi:10.1007/bf01732471 · Cited by 139
A method for constructing maximum parsimony ancestral amino acid sequences on a given network
Moore, G. W., Barnabas, J., & Goodman, M. (1973) · Journal of Theoretical Biology · doi:10.1016/0022-5193(73)90252-x · Cited by 137
Graham, R. L., & Foulds, L. R. (1982) · Mathematical Biosciences · doi:10.1016/0025-5564(82)90125-0 · Cited by 135
Voronoui Diagrams in $L_1 (L_\infty )$ Metrics with 2-Dimensional Storage Applications
Lee, D. T., & Wong, C. K. (1980) · SIAM Journal on Computing · doi:10.1137/0209017 · Cited by 126
Maculan, N. (1987) · North-Holland mathematics studies · doi:10.1016/s0304-0208(08)73236-5 · Cited by 112
Rectilinear steiner trees: Efficient special‐case algorithms
Aho, A. V., Garey, M. R., & Hwang, F. K. (1977) · Networks · doi:10.1002/net.3230070104 · Cited by 99
Self-citationA new global router for row-based layout
Lee, K.-W., & Sechen, C. (2003) · International Conference on Computer Aided Design · doi:10.1109/iccad.1988.122489 · Cited by 86
Cedergren, R., Sankoff, D., Larue, B., Grosjean, H., & Söil, D. (1981) · Critical Reviews in Biochemistry and Molecular Biology · doi:10.3109/10409238109108699 · Cited by 83
Applications of the Annealing Algorithm to Combinatorial Problems in Statistics
Lundy, M. E. (1985) · Biometrika · doi:10.1093/biomet/72.1.191 · Cited by 83
The NP-completeness column: An ongoing guide
Johnson, D. S. (1987) · Journal of Algorithms · doi:10.1016/0196-6774(87)90021-6 · Cited by 75
Georgakopoulos, G., & Papadimitriou, C. H. (1987) · Journal of Algorithms · doi:10.1016/0196-6774(87)90032-0 · Cited by 55
STEINER TREES, STEINER CIRCUITS AND THE INTERFERENCE PROBLEM IN BUILDING DESIGN
Smith, J. M., & Liebman, J. S. (1979) · Engineering Optimization · doi:10.1080/03052157908902401 · Cited by 48
A strategy for sequence phylogeny research
Sankoff, D., Cedergren, R., & McKay, W. (1982) · Nucleic Acids Research · doi:10.1093/nar/10.1.421 · Cited by 47
Gilbert, E. N. (1965) · Journal of the Society for Industrial and Applied Mathematics · doi:10.1137/0113021 · Cited by 46
A powerful global router: based on Steiner min-max trees
Chiang, C., Sarrafzadeh, M., & Wong, C. K. (2003) · International Conference on Computer Aided Design · doi:10.1109/iccad.1989.76892 · Cited by 45
Two probabilistic results on rectilinear steiner trees
Bern, M. W. (1988) · Algorithmica · doi:10.1007/bf01762114 · Cited by 42
Efficient Greedy Heuristics For Steiner Tree Problems Using Reolptimization And Super Modularity
Minoux, M. (1990) · INFOR Information Systems and Operational Research · doi:10.1080/03155986.1990.11732136 · Cited by 42
Resolving the query inference problem using Steiner trees
Wald, J. A., & Sorenson, P. G. (1984) · ACM Transactions on Database Systems · doi:10.1145/1270.1275 · Cited by 39
A Network Minimization Problem [Letter to the Editor]
Palermo, F. P. (1961) · IBM Journal of Research and Development · doi:10.1147/rd.54.0335 · Cited by 30
Lee, D. H. (1976) · Networks · doi:10.1002/net.3230060405 · Cited by 23
Maximum savings in the Steiner problem in phylogeny
Foulds, L. R. (1984) · Journal of Theoretical Biology · doi:10.1016/s0022-5193(84)80103-4 · Cited by 14
Werner, C. (1969) · Canadian Geographies / Géographies canadiennes · doi:10.1111/j.1541-0064.1969.tb00493.x · Cited by 13
An O (n2) heuristic algorithm for the directed Steiner minimal tree problem
Smith, J. M., & Liebman, J. S. (1980) · Applied Mathematical Modelling · doi:10.1016/0307-904x(80)90163-8 · Cited by 3
Testing the theory of evolution: A novel application of comibinatorial optimization
Foulds, L. R. (1986) · Discrete Applied Mathematics · doi:10.1016/0166-218x(86)90048-x · Cited by 2
Cited by
Chen, S., & Nahrstedt, K. (1998) · IEEE Network · doi:10.1109/65.752646 · Cited by 874
Distributionally Robust Stochastic Optimization with Wasserstein Distance
Gao, R., & Kleywegt, A. (2023) · Mathematics of Operations Research · doi:10.1287/moor.2022.1275 · Cited by 630
Performance optimization of VLSI interconnect layout
Cong, J., He, L., Koh, C.-K., & Madden, P. H. (1996) · Integration · doi:10.1016/s0167-9260(96)00008-9 · Cited by 334
Clever Support: Efficient Support Structure Generation for Digital Fabrication
Vanek, J., Galicia, J. A. G., & Benes, B. (2014) · Computer Graphics Forum · doi:10.1111/cgf.12437 · Cited by 268
Quantum circuit optimizations for NISQ architectures
Nash, B., Gheorghiu, V., & Mosca, M. (2020) · Quantum Science and Technology · doi:10.1088/2058-9565/ab79b1 · Cited by 139
Metadata
- Authors
- Hwang, F. K., & Richards, D. S.
- Venue
- Networks
- Publisher
- Wiley
- Published
- 1992-01
- Volume
- 22
- Issue
- 1
- Pages
- 55-89
- ISSN
- 0028-3045 (ISSN-L)
- 1097-0037
- OpenAlex
- W2042492403
- Cited by
- 663
- References
- 68
- FWCI
- 19.08
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.
