Paths, Trees, and Flowers

The Factorization of Linear Graphs

Tutte, W. T. (1947) · Journal of the London Mathematical Society · doi:10.1112/jlms/s1-22.2.107 · Cited by 945

The Theory of Graphs and its Applications.

Harary, F., & Berge, C. (1963) · Biometrika · doi:10.2307/2333777 · Cited by 603

TWO THEOREMS IN GRAPH THEORY

Berge, C. (1957) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.43.9.842 · Cited by 577

Some recent applications of the theory of linear inequalities to extremal combinatorial analysis

Hoffman, A. J. (1960) · Proceedings of symposia in applied mathematics · doi:10.1090/psapm/010/0114759 · Cited by 192

An algorithm for a minimum cover of a graph

Norman, R. Z., & Rabin, M. O. (1959) · Proceedings of the American Mathematical Society · doi:10.1090/s0002-9939-1959-0106853-5 · Cited by 115

Covers and packings in a family of sets

Edmonds, J. (1962) · Bulletin of the American Mathematical Society · doi:10.1090/s0002-9904-1962-10791-5 · Cited by 101

Large rainbow matchings in general graphs

Aharoni, R., Berger, E., Chudnovsky, M., Howard, D., & Seymour, P. D. (2019) · European Journal of Combinatorics · doi:10.1016/j.ejc.2019.01.012 · Cited by 24

Fully Dynamic Maximal Matching in $O(\log n)$ Update Time (Corrected Version)

Baswana, S., Gupta, M. K., & Sen, S. (2018) · SIAM Journal on Computing · doi:10.1137/16m1106158 · Cited by 24

Efficient and Incentive‐Compatible Liver Exchange

Ergin, H. I., Sönmez, T., & Ünver, M. U. (2020) · Econometrica · doi:10.3982/ecta16400 · Cited by 24

Balanced network flows. I. A unifying framework for design and analysis of matching algorithms

Fremuth‐Paeger, C., & Jungnickel, D. (1999) · Networks · doi:10.1002/(sici)1097-0037(199901)33:1 · Cited by 24

Exact combinatorial algorithms: Ground states of disordered systems

Alava, M. J., Duxbury, P. M., Moukarzel, C. F., & Rieger, H. (2001) · Phase transitions and critical phenomena · doi:10.1016/s1062-7901(01)80009-4 · Cited by 24

Local Unimodularity in the Matching Polytope

Hoffman, A. J., & Oppenheim, R. (1978) · Annals of discrete mathematics · doi:10.1016/s0167-5060(08)70333-9 · Cited by 24

Optimal set partitioning, matchings and lagrangian duality

Nemhauser, G. L., & Weber, G. (1979) · Naval Research Logistics Quarterly · doi:10.1002/nav.3800260401 · Cited by 24

A new linear programming algorithm — better or worse than the Simplex Method?

Lovász, L. (1980) · The Mathematical Intelligencer · doi:10.1007/bf03023055 · Cited by 24

Inverse form-finding for tensegrity structures

Dong, W., Stafford, P. J., & Ruiz-Teran, A. M. (2019) · Computers & Structures · doi:10.1016/j.compstruc.2019.01.009 · Cited by 23

Utility maximization data scheduling in drone-assisted vehicular networks

Fan, X., Liu, B., Huang, C., Wen, S., & Fu, B. (2021) · Computer Communications · doi:10.1016/j.comcom.2021.04.033 · Cited by 23

A Fast, Simpler Algorithm for the Matroid Parity Problem

Orlin, J. B. (2008) · Springer eBooks · doi:10.1007/978-3-540-68891-4_17 · Cited by 23

Analytic asymptotic performance of topological codes

Fowler, A. G. (2013) · Physical Review A · doi:10.1103/physreva.87.040301 · Cited by 28

Maximum independent sets in subclasses of -free graphs

Lozin, V., & Mosca, R. (2008) · Information Processing Letters · doi:10.1016/j.ipl.2008.11.005 · Cited by 23

Open Research Areas in Distance Geometry

Liberti, L., & Lavor, C. (2018) · Springer optimization and its applications · doi:10.1007/978-3-319-99142-9_11 · Cited by 23

Poor textural image tie point matching via graph theory

Xiuxiao Yuan, A., Chen, S., Yuan, W., & Cai, Y. (2017) · ISPRS Journal of Photogrammetry and Remote Sensing · doi:10.1016/j.isprsjprs.2017.04.015 · Cited by 23

Market design for living-donor organ exchanges: an economic policy perspective

Sönmez, T., & Ünver, M. U. (2017) · Oxford Review of Economic Policy · doi:10.1093/oxrep/grx048 · Cited by 23

Relations between the lower domination parameters and the chromatic number of a graph

Chellali, M., & Volkmann, L. (2003) · Discrete Mathematics · doi:10.1016/s0012-365x(03)00093-1 · Cited by 23

A shift-based sequencing method for twin-shuttle automated storage and retrieval systems

Dooly, D. R., & Lee, H. F. (2008) · IIE Transactions · doi:10.1080/07408170701730776 · Cited by 23

Zero-visibility cops and robber and the pathwidth of a graph

Dereniowski, D., Dyer, D., Tifenbach, R. M., & Yang, B. (2014) · Journal of Combinatorial Optimization · doi:10.1007/s10878-014-9712-6 · Cited by 23

Robot Path Planning for Dimensional Measurement in Automotive Manufacturing

Sheng, W., Xi, N., Song, M., & Chen, Y. (2005) · Journal of Manufacturing Science and Engineering · doi:10.1115/1.1870013 · Cited by 23

Convex Quadratic Programming Approach to the Maximum Matching Problem

Cardoso, D. M. (2001) · Journal of Global Optimization · doi:10.1023/a:1011276123981 · Cited by 23

Matching theory—a sampler: from Dénes König to the present

Plummer, M. D. (1992) · Discrete Mathematics · doi:10.1016/0012-365x(92)90640-2 · Cited by 24

What Would Edmonds Do? Augmenting Paths and Witnesses for Degree-Bounded MSTs

Chaudhuri, K., Rao, S. B., Riesenfeld, S. J., & Talwar, K. (2005) · Lecture notes in computer science · doi:10.1007/11538462_3 · Cited by 23

The decomposition of systems of procedures and algebraic equations

Sargent, R. W. H. (1978) · Lecture notes in mathematics · doi:10.1007/bfb0067704 · Cited by 23

Pipelined correlated minimum weight perfect matching of the surface code

Paler, A., & Fowler, A. G. (2023) · Quantum · doi:10.22331/q-2023-12-12-1205 · Cited by 22

Maximum Flow and Minimum-Cost Flow in Almost-Linear Time

Chen, L., Kyng, R., Liu, Y. P., Peng, R., Gutenberg, M. P., & Sachdeva, S. (2025) · Journal of the ACM · doi:10.1145/3728631 · Cited by 22

Karp–Sipser on Random Graphs with a Fixed Degree Sequence

Bohman, T., & FRIEZE, A. M. (2011) · Combinatorics Probability Computing · doi:10.1017/s0963548311000265 · Cited by 22

$$P\mathop{ =}\limits^{?}NP$$

Aaronson, S. (2016) · Springer eBooks · doi:10.1007/978-3-319-32162-2_1 · Cited by 40

A theoretical and computational equilibria analysis of a multi-player kidney exchange program

Carvalho, M., & Lodi, A. (2022) · European Journal of Operational Research · doi:10.1016/j.ejor.2022.05.027 · Cited by 27

Correcting non-independent and non-identically distributed errors with surface codes

Tiurev, K., Derks, P.-J. H. S., Roffe, J., Eisert, J., & Reiner, J.-M. (2023) · Quantum · doi:10.22331/q-2023-09-26-1123 · Cited by 34

Parafermions in a Kagome Lattice of Qubits for Topological Quantum Computation

Hutter, A., Wootton, J. R., & Loss, D. (2015) · Physical Review X · doi:10.1103/physrevx.5.041040 · Cited by 22

Breakdown of surface-code error correction due to coupling to a bosonic bath

Hutter, A., & Loss, D. (2014) · Physical Review A · doi:10.1103/physreva.89.042334 · Cited by 22

Local, distributed weighted matching on general and wireless topologies

Nieberg, T. (2008) · Foundations of Mobile Computing · doi:10.1145/1400863.1400880 · Cited by 22

On Some Combinatorial Optimization Problems : Algorithms and Complexity

Uppman, H. (2015) · Linköping University Electronic Press eBooks · doi:10.3384/diss.diva-116859 · Cited by 22

Low overhead Clifford gates from joint measurements in surface, color, and hyperbolic codes

Lavasani, A., & Barkeshli, M. (2018) · Physical Review A · doi:10.1103/physreva.98.052319 · Cited by 22

Least Cost Rumor Community Blocking optimization in Social Networks

Zheng, J., & Pan, L. (2018) · International Conference on Security of Smart Cities, Industrial Control System and Communications (SSIC) · doi:10.1109/ssic.2018.8556739 · Cited by 22

Distributed Contact Plan Design for GNSSs

Yan, Z., Fraire, J. A., Zhao, K., Yan, H., Madoery, P. G., Li, W., & Yang, H. (2019) · IEEE Transactions on Aerospace and Electronic Systems · doi:10.1109/taes.2019.2917492 · Cited by 22

Domination When the Stars Are Out

Hermelin, D., Mnich, M., van Leeuwen, E. J., & Woeginger, G. J. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-22006-7_39 · Cited by 22

Noise thresholds for the [4,2,2]-concatenated toric code

Criger, B., & Terhal, B. M. (2016) · Quantum Information and Computation · doi:10.26421/qic16.15-16-1 · Cited by 22

A Few Queries Go a Long Way: Information-Distortion Tradeoffs in Matching

Amanatidis, G., Birmpas, G., Filos-Ratsikas, A., & Voudouris, A. A. (2022) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1.12690 · Cited by 22

Efficient algorithms for finding maximal matching in graphs

Galil, Z. (1983) · Lecture notes in computer science · doi:10.1007/3-540-12727-5_4 · Cited by 22

A Comprehensive Analysis of Polyhedral Lift-and-Project Methods

Au, Y. H., & Tunçel, L. (2016) · SIAM Journal on Discrete Mathematics · doi:10.1137/130950173 · Cited by 22

Optimal Matching in Wireless Sensor Networks

Roumy, A., & Gesbert, D. (2007) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2007.909378 · Cited by 22

A Frontal Delaunay Quad Mesh Generator Using the L ∞ Norm

Remacle, J., Henrotte, F., Baudouin, T. C., Geuzaine, C., Béchet, É., Mouton, T., & Marchandise, É. (2011) · Springer eBooks · doi:10.1007/978-3-642-24734-7_25 · Cited by 22

Chapter 10 Complexity theoretic model theory and algebra

Cenzer, D., & Remmel, J. B. (1998) · Studies in logic and the foundations of mathematics · doi:10.1016/s0049-237x(98)80011-6 · Cited by 22

Acyclic orientations of a graph and chromatic and independence numbers

Deming, R. W. (1979) · Journal of Combinatorial Theory Series B · doi:10.1016/0095-8956(79)90048-0 · Cited by 22

Distance Constrained Labeling of Precolored Trees

Fiala, J., Kratochvı́l, J., & Proskurowski, A. (2001) · Lecture notes in computer science · doi:10.1007/3-540-45446-2_18 · Cited by 22

HybridGNN: A Self-Supervised Graph Neural Network for Efficient Maximum Matching in Bipartite Graphs

Pan, C.-H., Qu, Y., Yao, Y., & Wang, M. (2024) · Symmetry · doi:10.3390/sym16121631 · Cited by 21

Self-correcting quantum memory with a boundary

Hutter, A., Wootton, J. R., Röthlisberger, B., & Loss, D. (2012) · Physical Review A · doi:10.1103/physreva.86.052340 · Cited by 21

Finding a maximum matching in a sparse random graph in O ( n ) expected time

Chebolu, P., FRIEZE, A. M., & Melsted, P. (2010) · Journal of the ACM · doi:10.1145/1734213.1734218 · Cited by 21

Optimal Decisions for Organ Exchanges in a Kidney Paired Donation Program

Li, Y., Song, P. X.-K., Zhou, Y., Leichtman, A. B., Rees, M. A., & Kalbfleisch, J. D. (2013) · Statistics in Biosciences · doi:10.1007/s12561-013-9082-0 · Cited by 21

B-Matching for Spectral Clustering

Jebara, T., & Shchogolev, V. (2006) · Lecture notes in computer science · doi:10.1007/11871842_67 · Cited by 21

Implementing weighted b-matching algorithms

Müller‐Hannemann, M., & Schwartz, A. (2000) · ACM Journal of Experimental Algorithmics · doi:10.1145/351827.384250 · Cited by 21

Adjacency on combinatorial polyhedra

Matsui, T., & Tamura, S. (1995) · Discrete Applied Mathematics · doi:10.1016/0166-218x(94)00092-r · Cited by 21

On the maximum even factor in weakly symmetric graphs

Pap, G., & Szegő, L. (2004) · Journal of Combinatorial Theory Series B · doi:10.1016/j.jctb.2004.01.001 · Cited by 21

Implementation of O(nmlog n) Weighted Matchings in General Graphs. The Power of Data Structures

Mehlhorn, K., & Schäfer, G. (2001) · Lecture notes in computer science · doi:10.1007/3-540-44691-5_3 · Cited by 21

Algorithmic Aspects of Combinatorial Designs: A Survey

Colbourn, M. J. (1985) · North-Holland mathematics studies · doi:10.1016/s0304-0208(08)72976-1 · Cited by 21

b -Matchings in Trees

Goodman, S. E., Hedetniemi, S. T., & Tarjan, R. E. (1976) · SIAM Journal on Computing · doi:10.1137/0205009 · Cited by 21

P-Selective Self-Reducible Sets: A New Characterization of P

Buhrman, H., & Torenvliet, L. (1996) · Journal of Computer and System Sciences · doi:10.1006/jcss.1996.0062 · Cited by 21

A Survey of Integer Programming Emphasizing Computation and Relations among Models

Garfinkel, R., & Nemhauser, G. L. (1973) · Elsevier eBooks · doi:10.1016/b978-0-12-358350-5.50007-5 · Cited by 21

Dominating induced matchings in graphs containing no long claw

Hertz, A., Lozin, V., Ries, B., Zamaraev, V., & de Werra, D. (2017) · Journal of Graph Theory · doi:10.1002/jgt.22182 · Cited by 20

Matroid matching

Lee, J., Sviridenko, M. I., & Vondrák, J. (2010) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1806689.1806741 · Cited by 20

Global Contour Lines Reconstruction in Topographic Maps

Pouderoux, J., & Spinello, S. (2007) · IAPR International Conference on Document Analysis and Recognition (ICDAR) · doi:10.1109/icdar.2007.4377021 · Cited by 20

A simple linear expected time algorithm for finding a hamilton path

Thomason, A. (1989) · Discrete Mathematics · doi:10.1016/0012-365x(89)90100-3 · Cited by 20

CaCo: An Efficient Cauchy Coding Approach for Cloud Storage Systems

Zhang, G., Wu, G., Wang, S., Shu, J., Zheng, W., & Li, K. (2015) · IEEE Transactions on Computers · doi:10.1109/tc.2015.2428701 · Cited by 20

Maximum Matching in Regular and Almost Regular Graphs

Yuster, R. (2012) · Algorithmica · doi:10.1007/s00453-012-9625-7 · Cited by 20

Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs

Epstein, L., Halldórsson, M. M., Levin, A., & Shachnai, H. (2007) · Algorithmica · doi:10.1007/s00453-007-9161-z · Cited by 20

Struction revisited

Alexe, G., Hammer, P. L., Lozin, V., & de Werra, D. (2003) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(03)00388-3 · Cited by 20

Ground-state magnetization of Ising spin glasses

Barahona, F. (1994) · Physical review. B, Condensed matter · doi:10.1103/physrevb.49.12864 · Cited by 20

New primal and dual matching heuristics

J�nger, M., & Pulleyblank, W. R. (1995) · Algorithmica · doi:10.1007/bf01293485 · Cited by 20

High-fidelity magic-state preparation with a biased-noise architecture

Singh, S., Darmawan, A. S., Brown, B. J., & Puri, S. (2022) · Physical Review A · doi:10.1103/physreva.105.052410 · Cited by 24

PIKAChU: a Python-based informatics kit for analysing chemical units

Terlouw, B. R., Vromans, S. P. J. M., & Medema, M. H. (2022) · Journal of Cheminformatics · doi:10.1186/s13321-022-00616-5 · Cited by 19

Computing maximum matchings in temporal graphs

Mertzios, G. B., Molter, H., Niedermeier, R., Zamaraev, V., & Zschoche, P. (2023) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2023.04.005 · Cited by 19

Induced matchings in subcubic graphs without short cycles

Henning, M. A., & Rautenbach, D. (2013) · Discrete Mathematics · doi:10.1016/j.disc.2013.10.009 · Cited by 19

Virtual Machine packing algorithms for lower power consumption

Takahashi, S., Nakada, H., Takefusa, A., Kudoh, T., Shigeno, M., & Yoshise, A. (2012) · IEEE International Conference on Cloud Computing Technology and Science · doi:10.1109/cloudcom.2012.6427493 · Cited by 19

Efficient Simulation of Quantum Error Correction Under Coherent Error Based on the Nonunitary Free-Fermionic Formalism

Suzuki, Y., Fujii, K., & Koashi, M. (2017) · Physical Review Letters · doi:10.1103/physrevlett.119.190503 · Cited by 19

The role of entropy in topological quantum error correction

Beverland, M. E., Brown, B. J., Kastoryano, M. J., & Marolleau, Q. (2019) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/ab25de · Cited by 19

Cognitive and Computational Complexity: Considerations from Mathematical Problem Solving

Pantsar, M. (2019) · Erkenntnis · doi:10.1007/s10670-019-00140-3 · Cited by 21

Optimal User Pairing in Cache-Based NOMA Systems with Index Coding

Fu, Y., Shum, K. W., Sung, C. W., & Liu, Y. (2019) · International Conference on Communications · doi:10.1109/icc.2019.8761754 · Cited by 19

Finding Diverse Trees, Paths, and More

Hanaka, T., Kobayashi, Y., Kurita, K., & Otachi, Y. (2021) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v35i5.16495 · Cited by 19

Regularization-Based Coflow Scheduling in Optical Circuit Switches

Tan, H., Zhang, C., Xu, C., Li, Y., Han, Z., & Li, X. (2021) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2021.3058164 · Cited by 19

Coverings and delta-coverings

Bouchet, A. (1995) · Lecture notes in computer science · doi:10.1007/3-540-59408-6_54 · Cited by 19

The Vertex-Disjoint Triangles Problem

Guruswami, V., Rangan, C. P., Chang, M., Chang, G. J., & Wong, C. K. (1998) · Lecture notes in computer science · doi:10.1007/10692760_3 · Cited by 19

Reconstructing polygons from scanner data

Biedl, T., Durocher, S., & Snoeyink, J. S. (2010) · Theoretical Computer Science · doi:10.1016/j.tcs.2010.10.026 · Cited by 19

Minimum-maximal matching in series-parallel graphs

Richey, M. B., & Parker, R. (1988) · European Journal of Operational Research · doi:10.1016/0377-2217(88)90258-5 · Cited by 19

Parameterized Algorithms for Generalized Domination

Raman, V., Saurabh, S., & Srihari, S. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-85097-7_11 · Cited by 19

ε-Samples for Kernels

Phillips, J. M. (2013) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611973105.116 · Cited by 19

On the Power of Tree-Depth for Fully Polynomial FPT Algorithms

Iwata, Y., Ogasawara, T., & Ohsaka, N. (2018) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.stacs.2018.41 · Cited by 19

Finding long cycles in graphs

Marinari, E., Semerjian, G., & Kerrebroeck, V. V. (2007) · Physical Review E · doi:10.1103/physreve.75.066708 · Cited by 19

On thek-systems of a simple polytope

Joswig, M., Kaibel, V., & Körner, F. (2002) · Israel Journal of Mathematics · doi:10.1007/bf02773157 · Cited by 19

Subgraph Packing — A Survey

Loebl, M., & Poljak, S. (1990) · Physica-Verlag eBooks · doi:10.1007/978-3-642-46908-4_56 · Cited by 19

A Computable Economist’s Perspective on Computational Complexity

Velupillai, K. V. (2009) · Edward Elgar Publishing eBooks · doi:10.4337/9781781952665.00009 · Cited by 18

Reductions to 1–matching polyhedra

Aráoz, J., Cunningham, W. H., Edmonds, J., & Green‐Krótki, J. (1983) · Networks · doi:10.1002/net.3230130403 · Cited by 19

Von Neumann, Gödel and Complexity Theory

Urquhart, A. (2010) · Bulletin of Symbolic Logic · doi:10.2178/bsl/1294171130 · Cited by 18

Numerical Implementation of Just-In-Time Decoding in Novel Lattice Slices Through the Three-Dimensional Surface Code

Scruby, T. R., Browne, D. E., Webster, P., & Vasmer, M. (2022) · Quantum · doi:10.22331/q-2022-05-24-721 · Cited by 18

Between Shor and Steane: A Unifying Construction for Measuring Error Syndromes

Huang, S., & Brown, K. R. (2021) · Physical Review Letters · doi:10.1103/physrevlett.127.090505 · Cited by 18

Partitioning planar graphs: a fast combinatorial approach for max-cut

Liers, F., & Pardella, G. (2010) · Computational Optimization and Applications · doi:10.1007/s10589-010-9335-5 · Cited by 18

Fine-Grained Fast Field-Programmable Gate Array Scrubbing

Nazar, G. L., Santos, L. P., & Carro, L. (2014) · IEEE Transactions on Very Large Scale Integration (VLSI) Systems · doi:10.1109/tvlsi.2014.2330742 · Cited by 18

On channel-discontinuity-constraint routing in wireless networks

Sankararaman, S., Efrat, A., Srinivasan Ramasubramanian, D., & Agarwal, P. K. (2011) · Ad Hoc Networks · doi:10.1016/j.adhoc.2011.04.011 · Cited by 18

Topological quantum error correction in the Kitaev honeycomb model

Lee, Y.-C., Brell, C. G., & Flammia, S. T. (2017) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/aa7ee2 · Cited by 18

Matchings in Arbitrary Graphs

Brualdi, R. A. (1971) · Mathematical Proceedings of the Cambridge Philosophical Society · doi:10.1017/s0305004100046831 · Cited by 9

Using Blossoms to Find Maximum Matchings on Graphs ; CU-CS-056-74

Gabow, H. N. (1974) · CU Scholar (University of Colorado Boulder)

Maximum Matching

Mucha, M. (2008) · Encyclopedia of Algorithms · doi:10.1007/978-0-387-30162-4_225 · Cited by 1

J.-S. Sereni Matchings in Graphs 11/2009

(2015)

Algebraic Algorithms for Matching

Ivan, I., Virza, M., & Yuen, H. (2011)