The DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index.
An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
Abstract
The present paper shows how to construct a maximum matching in a bipartite graph with n vertices and m edges in a number of computation steps proportional to $(m + n)\sqrt n $.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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
The Hungarian method for the assignment problem
Kuhn, H. W. (1955) · Naval Research Logistics Quarterly · doi:10.1002/nav.3800020109 · Cited by 13,120
Edmonds, J. (1965) · Canadian Journal of Mathematics · doi:10.4153/cjm-1965-045-4 · Cited by 2,428
Berge, C. (1957) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.43.9.842 · Cited by 567
Cited by
Motwani, R., & Raghavan, P. (1995) · Cambridge University Press eBooks · doi:10.1017/cbo9780511814075 · Cited by 5,123
Controllability of complex networks
Liu, Y.-Y., Slotine, J.-J., & Barabási, A.-L. (2011) · Nature · doi:10.1038/nature10011 · Cited by 3,215
The complexity of computing the permanent
Valiant, L. G. (1979) · Theoretical Computer Science · doi:10.1016/0304-3975(79)90044-6 · Cited by 2,705
Partitioning Sparse Matrices with Eigenvectors of Graphs
Pothen, A., Simon, H. D., & Liou, K.-P. (1990) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/0611030 · Cited by 1,684
Handbook of Constraint Programming
(2006) · Foundations of Artificial Intelligence · doi:10.1016/s1574-6526(06)x8001-x · Cited by 1,483
The iSLIP scheduling algorithm for input-queued switches
McKeown, N. (1999) · IEEE/ACM Transactions on Networking · doi:10.1109/90.769767 · Cited by 1,185
On the Complexity of Timetable and Multicommodity Flow Problems
Even, S., Itai, A., & Shamir, A. (1976) · SIAM Journal on Computing · doi:10.1137/0205048 · Cited by 1,057
(1998) · Choice Reviews Online · doi:10.5860/choice.35-6287 · Cited by 904
Achieving 100% throughput in an input-queued switch
McKeown, N., Mekkittikul, A., Anantharam, V., & Walrand, J. (1999) · IEEE Transactions on Communications · doi:10.1109/26.780463 · Cited by 838
An O(v|v| c |E|) algoithm for finding maximum matching in general graphs
Micali, S., & Vazirani, V. V. (1980) · 21st Annual Symposium on Foundations of Computer Science (sfcs 1980) · doi:10.1109/sfcs.1980.12 · Cited by 822
Shock Graphs and Shape Matching
Siddiqi, K., Shokoufandeh, A., Dickinson, S. J., & Zucker, S. W. (1999) · International Journal of Computer Vision · doi:10.1023/a:1008102926703 · Cited by 756
On the Computational Complexity of Combinatorial Problems
Karp, R. M. (1975) · Networks · doi:10.1002/net.1975.5.1.45 · Cited by 711
Self-citationIntelligent multi-camera video surveillance: A review
Wang, X. (2013) · Pattern Recognition Letters · doi:10.1016/j.patrec.2012.07.005 · Cited by 694
A Survey of Automated Timetabling
Schaerf, A. (1999) · Artificial Intelligence Review · doi:10.1023/a:1006576209967 · Cited by 654
Control principles of complex systems
Liu, Y.-Y., & Barabási, A.-L. (2016) · Reviews of Modern Physics · doi:10.1103/revmodphys.88.035006 · Cited by 654
Edmonds polytopes and a hierarchy of combinatorial problems
Chvátal, V. (1973) · Discrete Mathematics · doi:10.1016/0012-365x(73)90167-2 · Cited by 624
Managing and Mining Graph Data
(2010) · Advances in Database Systems · doi:10.1007/978-1-4419-6045-0 · Cited by 594
Exact controllability of complex networks
Yuan, Z., Zhao, C., Di, Z., Wang, W.-X., & Lai, Y.-C. (2013) · Nature Communications · doi:10.1038/ncomms3447 · Cited by 565
Algorithmics of Matching Under Preferences
Manlove, D. F. (2013) · Series on Theoretical Computer Science · doi:10.1142/8591 · Cited by 515
Efficient algorithms for finding maximum matching in graphs
Galil, Z. (1986) · ACM Computing Surveys · doi:10.1145/6462.6502 · Cited by 461
Graphs-at-a-time: query language and access methods for graph databases
He, H., & Singh, A. K. (2008) · Proceedings of the 2008 ACM SIGMOD international conference on Management of data · doi:10.1145/1376616.1376660 · Cited by 450
On the complexity of time table and multi-commodity flow problems
Even, S., Itai, A., & Shamir, A. (1975) · 16th Annual Symposium on Foundations of Computer Science (sfcs 1975) · doi:10.1109/sfcs.1975.21 · Cited by 431
Faster Scaling Algorithms for Network Problems
Gabow, H. N., & Tarjan, R. E. (1989) · SIAM Journal on Computing · doi:10.1137/0218069 · Cited by 414
A Local-Ratio Theorem for Approximating the Weighted Vertex Cover Problem
Bar-Yehuda, R., & Even, S. (1985) · North-Holland Mathematics Studies · doi:10.1016/s0304-0208(08)73101-3 · Cited by 404
Target control of complex networks
Gao, J., Liu, Y.-Y., D'Souza, R. M., & Barabási, A.-L. (2014) · Nature Communications · doi:10.1038/ncomms6415 · Cited by 404
Control Profiles of Complex Networks
Ruths, J., & Ruths, D. (2014) · Science · doi:10.1126/science.1242063 · Cited by 391
Addressing the minimum fleet problem in on-demand urban mobility
Vazifeh, M. M., Santi, P., Resta, G., Strogatz, S. H., & Ratti, C. (2018) · Nature · doi:10.1038/s41586-018-0095-1 · Cited by 389
Online Matching and Ad Allocation
Mehta, A. (2010) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000057 · Cited by 387
On Algorithms For Permuting Large Entries to the Diagonal of a Sparse Matrix
Duff, I. S., & Koster, J. (2001) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479899358443 · Cited by 358
Linear Assignment Problems and Extensions
Burkard, R. E., & Çela, E. (1999) · Handbook of Combinatorial Optimization · doi:10.1007/978-1-4757-3023-4_2 · Cited by 330
Bioinspired computation in combinatorial optimization: algorithms and their computational complexity
Neumann, F., & Witt, C. (2012) · Proceedings of the 14th annual conference companion on Genetic and evolutionary computation · doi:10.1145/2330784.2330928 · Cited by 319
Faster scaling algorithms for general graph matching problems
Gabow, H. N., & Tarjan, R. E. (1991) · Journal of the ACM · doi:10.1145/115234.115366 · Cited by 301
Closure-Tree: An Index Structure for Graph Queries
He, H., & Singh, A. K. (2006) · 22nd International Conference on Data Engineering (ICDE'06) · doi:10.1109/icde.2006.37 · Cited by 293
Javed, O., Shafique, K., Rasheed, Z., & Shah, M. (2008) · Computer Vision and Image Understanding · doi:10.1016/j.cviu.2007.01.003 · Cited by 291
An O (N2.5) algorithm for maximum matching in general graphs
Even, S., & Kariv, O. (1975) · 16th Annual Symposium on Foundations of Computer Science (sfcs 1975) · doi:10.1109/sfcs.1975.5 · Cited by 287
On Databases with Incomplete Information
Lipski, W. (1981) · Journal of the ACM · doi:10.1145/322234.322239 · Cited by 275
Linear-Time Approximation for Maximum Weight Matching
Duan, R., & Pettie, S. (2014) · Journal of the ACM · doi:10.1145/2529989 · Cited by 265
A survey of sparse matrix research
Duff, I. S. (1977) · Proceedings of the IEEE · doi:10.1109/proc.1977.10514 · Cited by 262
Hucka, M., Bergmann, F. T., Chaouiya, C., Dräger, A., Hoops, S., Keating, S. M., König, M., Novère, N. L., Myers, C. J., Olivier, B. G., et al. (2019) · Journal of Integrative Bioinformatics · doi:10.1515/jib-2019-0021 · Cited by 258
Vinayagam, A., Gibson, T. E., Lee, H.-J., Yilmazel, B., Roesel, C., Hu, Y., Kwon, Y., Sharma, A., Liu, Y.-Y., Perrimon, N., et al. (2016) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1603992113 · Cited by 257
The Design and Use of Algorithms for Permuting Large Entries to the Diagonal of Sparse Matrices
Duff, I. S., & Koster, J. (1999) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479897317661 · Cited by 254
Tsuji, S., Hase, T., Yachie-Kinoshita, A., Nishino, T., Ghosh, S., Kikuchi, M., Shimokawa, K., Aburatani, H., Kitano, H., & Tanaka, H. (2021) · Alzheimer's Research & Therapy · doi:10.1186/s13195-021-00826-3 · Cited by 75
Metadata
- Authors
- Hopcroft, J. E., & Karp, R. M.
- Venue
- SIAM Journal on Computing
- Published
- 1973-12
- Volume
- 2
- Issue
- 4
- Pages
- 225-231
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W2157529519
- Cited by
- 2,802
- References
- 3
- FWCI
- 11.49
- 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.