The DOI matches its Crossref record; 2 of the 2 references it cites were found in a registry or an index.
A note on two problems in connexion with graphs
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
On the shortest spanning subtree of a graph and the traveling salesman problem
Kruskal, J. B. (1956) · Proceedings of the American Mathematical Society · doi:10.1090/s0002-9939-1956-0078686-7 · Cited by 5,088
Formal Procedures for Connecting Terminals with a Minimum Total Wire Length
Loberman, H., & Weinberger, A. (1957) · Journal of the ACM · doi:10.1145/320893.320896 · Cited by 70
Cited by
Cortical Surface-Based Analysis
Dale, A. M., Fischl, B., & Sereno, M. I. (1999) · NeuroImage · doi:10.1006/nimg.1998.0395 · Cited by 10,910
Cortical Surface-Based Analysis
Fischl, B., Sereno, M. I., & Dale, A. M. (1999) · NeuroImage · doi:10.1006/nimg.1998.0396 · Cited by 6,147
Network analysis: An integrative approach to the structure of psychopathology
Borsboom, D., & Cramer, A. O. J. (2013) · Annual Review of Clinical Psychology · doi:10.1146/annurev-clinpsy-050212-185608 · Cited by 4,359
Node centrality in weighted networks: Generalizing degree and shortest paths
Opsahl, T., Agneessens, F., & Skvoretz, J. (2010) · Social Networks · doi:10.1016/j.socnet.2010.03.006 · Cited by 3,718
Pregel: a system for large-scale graph processing
Malewicz, G., Austern, M. H., Bik, A. J. C., Dehnert, J. C., Horn, I., Leiser, N., & Czajkowski, G. (2010) · Proceedings of the 2010 ACM SIGMOD International Conference on Management of data · doi:10.1145/1807167.1807184 · Cited by 3,515
Sridharan, D., Levitin, D. J., & Menon, V. (2008) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0800005105 · Cited by 2,892
Fibonacci heaps and their uses in improved network optimization algorithms
Fredman, M. L., & Tarjan, R. E. (1987) · Journal of the ACM · doi:10.1145/28869.28874 · Cited by 2,656
Finding the K Shortest Loopless Paths in a Network
Yen, J. Y. (1971) · Management Science · doi:10.1287/mnsc.17.11.712 · Cited by 2,618
A Survey of Motion Planning and Control Techniques for Self-Driving Urban Vehicles
Paden, B., Cap, M., Yong, S. Z., Yershov, D., & Frazzoli, E. (2016) · IEEE Transactions on Intelligent Vehicles · doi:10.1109/tiv.2016.2578706 · Cited by 2,585
Automated identification and indexing of dislocations in crystal interfaces
Stukowski, A., Bulatov, V. V., & Arsenlis, A. (2012) · Modelling and Simulation in Materials Science and Engineering · doi:10.1088/0965-0393/20/8/085007 · Cited by 2,375
The ellipsoid method and its consequences in combinatorial optimization
Grötschel, M., Lovász, L., & Schrijver, A. (1981) · Combinatorica · doi:10.1007/bf02579273 · Cited by 2,011
Algorithms and tools for high-throughput geometry-based analysis of crystalline porous materials
Willems, T. F., Rycroft, C. H., Kazi, M., Meza, J. C., & Haranczyk, M. (2012) · Microporous and Mesoporous Materials · doi:10.1016/j.micromeso.2011.08.020 · Cited by 1,925
Robust discrete optimization and network flows
Bertsimas, D., & Sim, M. (2003) · Mathematical Programming · doi:10.1007/s10107-003-0396-4 · Cited by 1,799
Extended tight‐binding quantum chemistry methods
Bannwarth, C., Caldeweyher, E., Ehlert, S., Hansen, A., Pracht, P., Seibert, J., Spicher, S., & Grimme, S. (2021) · WIREs Computational Molecular Science · doi:10.1002/wcms.1493 · Cited by 1,662
EXPERT SYSTEMS WITH APPLICATIONS
(2005) · Expert Systems with Applications · doi:10.1016/j.eswa.2004.10.010 · Cited by 1,656
Sethian, J. A. (1999) · SIAM Review · doi:10.1137/s0036144598347059 · Cited by 1,602
AntNet: Distributed Stigmergetic Control for Communications Networks
Di Caro, G., & Dorigo, M. (1998) · Journal of Artificial Intelligence Research · doi:10.1613/jair.530 · Cited by 1,579
LANDSCAPE CONNECTIVITY: A GRAPH-THEORETIC PERSPECTIVE
Urban, D., & Keitt, T. (2001) · Ecology · doi:10.1890/0012-9658(2001)082[1205:lcagtp]2.0.co;2 · Cited by 1,486
The Traveling-Salesman Problem and Minimum Spanning Trees
Held, M., & Karp, R. M. (1970) · Operations Research · doi:10.1287/opre.18.6.1138 · Cited by 1,440
Benchmarking atlas-level data integration in single-cell genomics
Luecken, M. D., Büttner, M., Chaichoompu, K., Danese, A., Interlandi, M., Mueller, M. F., Strobl, D. C., Zappia, L., Dugas, M., Colomé-Tatché, M., et al. (2022) · Nature Methods · doi:10.1038/s41592-021-01336-8 · Cited by 1,438
CAVER 3.0: A Tool for the Analysis of Transport Pathways in Dynamic Protein Structures
Chovancova, E., Pavelka, A., Benes, P., Strnad, O., Brezovsky, J., Kozlikova, B., Gora, A., Sustr, V., Klvana, M., Medek, P., et al. (2012) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1002708 · Cited by 1,411
The Watershed Transform: Definitions, Algorithms and Parallelization Strategies
Roerdink, J. B. T. M., & Meijster, A. (2000) · Fundamenta Informaticae · doi:10.3233/fi-2000-411207 · Cited by 1,372
The Design of Approximation Algorithms
Williamson, D. P., & Shmoys, D. B. (2011) · Cambridge University Press eBooks · doi:10.1017/cbo9780511921735 · Cited by 1,301
A shortest augmenting path algorithm for dense and sparse linear assignment problems
Jonker, R., & Volgenant, A. (1987) · Computing · doi:10.1007/bf02278710 · Cited by 1,230
Scale-free networks in cell biology
Albert, R. (2005) · Journal of Cell Science · doi:10.1242/jcs.02714 · Cited by 1,215
Badue, C., Guidolini, R., Carneiro, R. V., Azevedo, P., Cardoso, V. B., Forechi, A., Jesus, L., Berriel, R., Paixão, T. M., Mutz, F., et al. (2021) · Expert Systems with Applications · doi:10.1016/j.eswa.2020.113816 · Cited by 1,209
The LEDA platform for combinatorial and geometric computing
Mehlhorn, K., Näher, S., & Uhrig, C. (1997) · Lecture Notes in Computer Science · doi:10.1007/3-540-63165-8_161 · Cited by 1,199
A fast algorithm for Steiner trees
Kou, L., Markowsky, G., & Berman, L. (1981) · Acta Informatica · doi:10.1007/bf00288961 · Cited by 1,188
Vital nodes identification in complex networks
Lü, L., Chen, D., Ren, X.-L., Zhang, Q.-M., Zhang, Y.-C., & Zhou, T. (2016) · Physics Reports · doi:10.1016/j.physrep.2016.06.007 · Cited by 1,183
A global map of travel time to cities to assess inequalities in accessibility in 2015
Weiss, D. J., Nelson, A., Gibson, H. S., Temperley, W., Peedell, S., Lieber, A., Hancher, M., Poyart, E., Belchior, S., Fullman, N., et al. (2018) · Nature · doi:10.1038/nature25181 · Cited by 1,169
Artificial Intelligence: A New Synthesis
(1998) · Elsevier eBooks · doi:10.1016/c2009-0-27773-7 · Cited by 1,163
Faber, B. (2014) · The Review of Economic Studies · doi:10.1093/restud/rdu010 · Cited by 1,060
Efficient Algorithms for Shortest Paths in Sparse Networks
Johnson, D. B. (1977) · Journal of the ACM · doi:10.1145/321992.321993 · Cited by 1,041
Web-Based Database for Facial Expression Analysis
Pantic, M., Valstar, M., Rademaker, R., & Maat, L. (2005) · 2005 IEEE International Conference on Multimedia and Expo · doi:10.1109/icme.2005.1521424 · Cited by 1,039
The traveling-salesman problem and minimum spanning trees: Part II
Held, M., & Karp, R. M. (1971) · Mathematical Programming · doi:10.1007/bf01584070 · Cited by 1,018
Multiple Object Tracking Using K-Shortest Paths Optimization
Berclaz, J., Fleuret, F., Turetken, E., & Fua, P. (2011) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2011.21 · Cited by 1,015
An Appraisal of Some Shortest-Path Algorithms
Dreyfus, S. E. (1969) · Operations Research · doi:10.1287/opre.17.3.395 · Cited by 1,002
State of the aRt personality research: A tutorial on network analysis of personality data in R
Costantini, G., Epskamp, S., Borsboom, D., Perugini, M., Mõttus, R., Waldorp, L. J., & Cramer, A. O. J. (2015) · Journal of Research in Personality · doi:10.1016/j.jrp.2014.07.003 · Cited by 982
Liftoff: accurate mapping of gene annotations
Shumate, A., & Salzberg, S. L. (2021) · Bioinformatics · doi:10.1093/bioinformatics/btaa1016 · Cited by 979
A review of 3D vessel lumen segmentation techniques: Models, features and extraction schemes
Lesage, D., Angelini, E. D., Bloch, I., & Funka-Lea, G. (2009) · Medical Image Analysis · doi:10.1016/j.media.2009.07.011 · Cited by 920
Discrete Choice Methods and their Applications to Short Term Travel Decisions
Ben-Akiva, M., & Bierlaire, M. (1999) · International Series in Operations Research & Management Science · doi:10.1007/978-1-4615-5203-1_2 · Cited by 908
(1998) · Choice Reviews Online · doi:10.5860/choice.35-6287 · Cited by 904
Betzel, R. F., Byrge, L., He, Y., Goñi, J., Zuo, X.-N., & Sporns, O. (2014) · NeuroImage · doi:10.1016/j.neuroimage.2014.07.067 · Cited by 807
AnO(ND) difference algorithm and its variations
Myers, E. W. (1986) · Algorithmica · doi:10.1007/bf01840446 · Cited by 893
Topology representing networks
Martinetz, T., & Schulten, K. (1994) · Neural Networks · doi:10.1016/0893-6080(94)90109-0 · Cited by 883
Chen, S., & Nahrstedt, K. (1998) · IEEE Network · doi:10.1109/65.752646 · Cited by 874
A Unified Framework for Street-View Panorama Stitching
Li, L., Yao, J., Xie, R., Xia, M., & Zhang, W. (2016) · Sensors · doi:10.3390/s17010001 · Cited by 873
Routing and scheduling of vehicles and crews
Raff, S. (1983) · Computers & Operations Research · doi:10.1016/0305-0548(83)90030-8 · Cited by 867
LoRDEC: accurate and efficient long read error correction
Salmela, L., & Rivals, E. (2014) · Bioinformatics · doi:10.1093/bioinformatics/btu538 · Cited by 844
A practical guide to linking brain-wide gene expression and neuroimaging data
Arnatkevic̆iūtė, A., Fulcher, B. D., & Fornito, A. (2019) · NeuroImage · doi:10.1016/j.neuroimage.2019.01.011 · Cited by 838
Adaptive reconfiguration of fractal small-world human brain functional networks
Bassett, D. S., Meyer-Lindenberg, A., Achard, S., Duke, T., & Bullmore, E. (2006) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0606005103 · Cited by 814
Shortest-Path Kernels on Graphs
Borgwardt, K. M., & Kriegel, H. (2006) · Fifth IEEE International Conference on Data Mining (ICDM'05) · doi:10.1109/icdm.2005.132 · Cited by 837
Gross motion planning—a survey
Hwang, Y. K., & Ahuja, N. (1992) · ACM Computing Surveys · doi:10.1145/136035.136037 · Cited by 826
Fifty Years of MIMO Detection: The Road to Large-Scale MIMOs
Yang, S., & Hanzo, L. (2015) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2015.2475242 · Cited by 814
On the History of the Minimum Spanning Tree Problem
Graham, R. L., & Hell, P. (1985) · IEEE Annals of the History of Computing · doi:10.1109/mahc.1985.10011 · Cited by 813
Using graph theory to analyze biological networks
Pavlopoulos, G. A., Secrier, M., Moschopoulos, C. N., Soldatos, T. G., Kossida, S., Aerts, J., Schneider, R., & Bagos, P. G. (2011) · BioData Mining · doi:10.1186/1756-0381-4-10 · Cited by 791
Sampling-Based Robot Motion Planning: A Review
Elbanhawi, M., & Simic, M. (2014) · IEEE Access · doi:10.1109/access.2014.2302442 · Cited by 786
Intelligent scissors for image composition
Mortensen, E. N., & Barrett, W. A. (1995) · Proceedings of the 22nd annual conference on Computer graphics and interactive techniques - SIGGRAPH '95 · doi:10.1145/218380.218442 · Cited by 778
Cajigas, I. J., Tushev, G., Will, T. J., tom Dieck, S., Fuerst, N., & Schuman, E. M. (2012) · Neuron · doi:10.1016/j.neuron.2012.02.036 · Cited by 709
Influence Maximization in Near-Linear Time: A Martingale Approach
Tang, Y., Shi, Y., & Xiao, X. (2015) · Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data · doi:10.1145/2723372.2723734 · Cited by 768
Importance and exposure in road network vulnerability analysis
Jenelius, E., Petersen, T., & Mattsson, L.-G. (2006) · Transportation Research Part A: Policy and Practice · doi:10.1016/j.tra.2005.11.003 · Cited by 746
Shortest paths algorithms: Theory and experimental evaluation
Cherkassky, B. V., Goldberg, A. V., & Radzik, T. (1996) · Mathematical Programming · doi:10.1007/bf02592101 · Cited by 743
Ant-Based Load Balancing in Telecommunications Networks
Schoonderwoerd, R., Holland, O. E., Bruten, J. L., & Rothkrantz, L. J. M. (1997) · Adaptive Behavior · doi:10.1177/105971239700500203 · Cited by 739
Chiu, S. J., Li, X. T., Nicholas, P., Toth, C. A., Izatt, J. A., & Farsiu, S. (2010) · Optics Express · doi:10.1364/oe.18.019413 · Cited by 733
Mitchell, J. S. B., Mount, D. M., & Papadimitriou, C. H. (1987) · SIAM Journal on Computing · doi:10.1137/0216045 · Cited by 720
The Spatial Semantic Hierarchy
Kuipers, B. (2000) · Artificial Intelligence · doi:10.1016/s0004-3702(00)00017-5 · Cited by 726
Computing the shortest path: A search meets graph theory
Goldberg, A. V., & Harrelson, C. (2005) · doi:10.5555/1070432.1070455 · Cited by 719
Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks
Geisberger, R., Sanders, P., Schultes, D., & Delling, D. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-68552-4_24 · Cited by 714
Peng, H., Ruan, Z., Long, F., Simpson, J. H., & Myers, E. W. (2010) · Nature Biotechnology · doi:10.1038/nbt.1612 · Cited by 707
A survey of graph edit distance
Gao, X., Xiao, B., Tao, D., & Li, X. (2010) · Pattern Analysis and Applications · doi:10.1007/s10044-008-0141-y · Cited by 704
The New Routing Algorithm for the ARPANET
McQuillan, J., Richer, I., & Rosen, E. (1980) · IEEE Transactions on Communications · doi:10.1109/tcom.1980.1094721 · Cited by 686
Suurballe, J. W. (1974) · Networks · doi:10.1002/net.3230040204 · Cited by 685
PathFinder: a negotiation-based performance-driven router for FPGAs
McMurchie, L., & Ebeling, C. (1995) · Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays · doi:10.1145/201310.201328 · Cited by 683
A Review of Motion Planning for Highway Autonomous Driving
Claussmann, L., Revilloud, M., Gruyer, D., & Glaser, S. (2020) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2019.2913998 · Cited by 670
Multivariate Generalizations of the Wald-Wolfowitz and Smirnov Two-Sample Tests
Friedman, J. H., & Rafsky, L. C. (1979) · The Annals of Statistics · doi:10.1214/aos/1176344722 · Cited by 665
Perception, Planning, Control, and Coordination for Autonomous Vehicles
Pendleton, S., Andersen, H., Du, X., Shen, X., Meghjani, M., Eng, Y., Rus, D., & Ang, M. (2017) · Machines · doi:10.3390/machines5010006 · Cited by 657
(2005) · Choice Reviews Online · doi:10.5860/choice.42-2854b · Cited by 639
Illuminating G-Protein-Coupling Selectivity of GPCRs
Inoue, A., Raimondi, F., Kadji, F. M. N., Singh, G., Kishi, T., Uwamizu, A., Ono, Y., Shinjo, Y., Ishida, S., Arang, N., et al. (2019) · Cell · doi:10.1016/j.cell.2019.04.044 · Cited by 638
(2002) · elib (German Aerospace Center) · Cited by 632
Global Minimum for Active Contour Models: A Minimal Path Approach
Cohen, L. D., & Kimmel, R. (1997) · International Journal of Computer Vision · doi:10.1023/a:1007922224810 · Cited by 625
The image foresting transform: theory, algorithms, and applications
Falcao, A. X., Stolfi, J., & de Alencar Lotufo, R. (2004) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2004.1261076 · Cited by 614
New Stories of Zeolite Structures: Their Descriptions, Determinations, Predictions, and Evaluations
Li, Y., & Yu, J. (2014) · Chemical Reviews · doi:10.1021/cr500010r · Cited by 603
Steiner problem in networks: A survey
Winter, P. (1987) · Networks · doi:10.1002/net.3230170203 · Cited by 599
SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge
Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E., & Virza, M. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-40084-1_6 · Cited by 598
A Review of Nonlinear Hyperspectral Unmixing Methods
Heylen, R., Parente, M., & Gader, P. (2014) · IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing · doi:10.1109/jstars.2014.2320576 · Cited by 591
Towards realistic mobility models for mobile ad hoc networks
Jardosh, A., Belding-Royer, E. M., Almeroth, K. C., & Suri, S. (2003) · Proceedings of the 9th annual international conference on Mobile computing and networking · doi:10.1145/938985.939008 · Cited by 594
Managing and Mining Graph Data
(2010) · Advances in Database Systems · doi:10.1007/978-1-4419-6045-0 · Cited by 594
Social Media Mining: An Introduction
Zafarani, R., Abbasi, M. A., & Liu, H. (2014) · Cambridge University Press eBooks · doi:10.1017/cbo9781139088510 · Cited by 592
An Incremental Self-Deployment Algorithm for Mobile Sensor Networks
Howard, A., Matarić, M. J., & Sukhatme, G. S. (2002) · Autonomous Robots · doi:10.1023/a:1019625207705 · Cited by 591
Motion Planning for Autonomous Driving: The State of the Art and Future Perspectives
Teng, S., Hu, X., Deng, P., Li, B., Li, Y., Ai, Y., Yang, D., Li, L., Xuanyuan, Z., Zhu, F., et al. (2023) · IEEE Transactions on Intelligent Vehicles · doi:10.1109/tiv.2023.3274536 · Cited by 590
Topological Analysis of Urban Street Networks
Jiang, B., & Claramunt, C. (2004) · Environment and Planning B: Planning and Design · doi:10.1068/b306 · Cited by 586
False rumors detection on Sina Weibo by propagation structures
Wu, K., Yang, S., & Zhu, K. Q. (2015) · 2015 IEEE 31st International Conference on Data Engineering · doi:10.1109/icde.2015.7113322 · Cited by 585
Bright spots among the world’s coral reefs
Cinner, J. E., Huchery, C., MacNeil, M. A., Graham, N. A. J., McClanahan, T. R., Maina, J., Maire, E., Kittinger, J. N., Hicks, C. C., Mora, C., et al. (2016) · Nature · doi:10.1038/nature18607 · Cited by 572
Route Planning in Transportation Networks
Bast, H., Delling, D., Goldberg, A., Müller-Hannemann, M., Pajor, T., Sanders, P., Wagner, D., & Werneck, R. F. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-49487-6_2 · Cited by 610
Quantifying the lag time to detect barriers in landscape genetics
LANDGUTH, E. L., CUSHMAN, S. A., SCHWARTZ, M. K., McKELVEY, K. S., MURPHY, M., & LUIKART, G. (2010) · Molecular Ecology · doi:10.1111/j.1365-294x.2010.04808.x · Cited by 567
A history of graph entropy measures
Dehmer, M., & Mowshowitz, A. (2011) · Information Sciences · doi:10.1016/j.ins.2010.08.041 · Cited by 565
Two Retinotopic Visual Areas in Human Lateral Occipital Cortex
Larsson, J., & Heeger, D. J. (2006) · The Journal of Neuroscience · doi:10.1523/jneurosci.1657-06.2006 · Cited by 564
DeepRoadMapper: Extracting Road Topology from Aerial Images
Mattyus, G., Luo, W., & Urtasun, R. (2017) · 2017 IEEE International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2017.372 · Cited by 560
Faster algorithms for the shortest path problem
Ahuja, R. K., Mehlhorn, K., Orlin, J., & Tarjan, R. E. (1990) · Journal of the ACM · doi:10.1145/77600.77615 · Cited by 554
Trafficking Networks and the Mexican Drug War
Dell, M. (2015) · American Economic Review · doi:10.1257/aer.20121637 · Cited by 553
Metadata
- Authors
- Dijkstra, E. W.
- Venue
- Numerische Mathematik
- Published
- 1959-12
- Volume
- 1
- Issue
- 1
- Pages
- 269-271
- ISSN
- 0029-599X (ISSN-L)
- 0945-3245
- OpenAlex
- W2169528473
- Cited by
- 24,043
- References
- 2
- FWCI
- 0.61
- 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.