The DOI matches its Crossref record; 11 of the 11 references it cites were found in a registry or an index.
The Complexity of Computing Steiner Minimal Trees
Abstract
It is shown that the problem of computing Steiner minimal trees for general planar point sets is inherently at least as difficult as any of the $NP$-complete problems (a well known class of computationally intractable problems). This effectively destroys any hope for finding an efficient algorithm for this problem.
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
The Design and Analysis of Computer Algorithms
Aho, A. V., & Hopcroft, J. E. (1974) · CERN Document Server (European Organization for Nuclear Research) · Cited by 9,403
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
Self-citationShamos, 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
On the Computational Complexity of Combinatorial Problems
Karp, R. M. (1975) · Networks · doi:10.1002/net.1975.5.1.45 · Cited by 711
Gilbert, E. N., & Pollak, H. O. (1968) · SIAM Journal on Applied Mathematics · doi:10.1137/0116001 · Cited by 690
On Steiner’s Problem with Rectilinear Distance
Hanan, M. (1966) · SIAM Journal on Applied Mathematics · doi:10.1137/0114025 · Cited by 623
On Steiner Minimal Trees with Rectilinear Distance
Hwang, F. K. (1976) · SIAM Journal on Applied Mathematics · doi:10.1137/0130013 · Cited by 424
Melzak, Z. A. (1961) · Canadian Mathematical Bulletin · doi:10.4153/cmb-1961-016-2 · Cited by 281
Design automation of digital systems
Breuer, M. A. (1972) · CERN Document Server (European Organization for Nuclear Research) · Cited by 175
Cited by
Handbook of Combinatorial Optimization
(1999) · Springer eBooks · doi:10.1007/978-1-4757-3023-4 · Cited by 1,216
(1998) · Choice Reviews Online · doi:10.5860/choice.35-6287 · Cited by 904
Hwang, F. K., & Richards, D. S. (1992) · Networks · doi:10.1002/net.3230220105 · Cited by 663
GRANT, T., FROST, D. R., CALDWELL, J. P., GAGLIARDO, R., HADDAD, C. F. B., KOK, P. J. R., MEANS, D. B., NOONAN, B. P., SCHARGEL, W. E., & WHEELER, W. C. (2006) · Bulletin of the American Museum of Natural History · doi:10.1206/0003-0090(2006)299[1:psodfa]2.0.co;2 · Cited by 578
Geometric Shortest Paths and Network Optimization
Mitchell, J. S. B. (2000) · Handbook of Computational Geometry · doi:10.1016/b978-044482537-7/50016-4 · Cited by 427
Some NP-complete geometric problems
Garey, M. R., Graham, R. L., & Johnson, D. S. (1976) · Proceedings of the eighth annual ACM symposium on Theory of computing - STOC '76 · doi:10.1145/800113.803626 · Cited by 400
Self-citationMoore, C., & Mertens, S. (2011) · doi:10.1093/acprof:oso/9780199233212.001.0001 · Cited by 347
Application of statistical mechanics to NP-complete problems in combinatorial optimisation
Fu, Y., & Anderson, P. W. (1986) · Journal of Physics A: Mathematical and General · doi:10.1088/0305-4470/19/9/033 · Cited by 317
Line-of-sight communication on terrain models
De Floriani, L., Marzano, P., & Puppo, E. (1994) · International journal of geographical information systems · doi:10.1080/02693799408902004 · Cited by 124
NODLINK: An Online System for Fine-Grained APT Attack Detection and Investigation
Li, S., Dong, F., Xiao, X., Wang, H., Shao, F., Chen, J., Guo, Y., Chen, X., & Li, D. (2024) · Proceedings 2024 Network and Distributed System Security Symposium · doi:10.14722/ndss.2024.23204 · Cited by 45
A Genetic Algorithm for Solving the Euclidean Non-Uniform Steiner Tree Problem
Frommer, I., & Golden, B. (2007) · Operations Research/Computer Science Interfaces Series · doi:10.1007/978-0-387-48793-9_3 · Cited by 3
Metadata
- Authors
- Garey, M. R., Graham, R. L., & Johnson, D. S.
- Venue
- SIAM Journal on Applied Mathematics
- Published
- 1977-06
- Volume
- 32
- Issue
- 4
- Pages
- 835-859
- ISSN
- 0036-1399 (ISSN-L)
- 1095-712X
- OpenAlex
- W2060380213
- Cited by
- 576
- References
- 11
- FWCI
- 3.95
- 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.