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

Matching, Allocation, and Exchange of Discrete Resources

Sönmez, T., & Ünver, M. U. (2011) · Handbook of social economics · doi:10.1016/b978-0-444-53187-2.00017-6 · Cited by 189

High-Threshold Fault-Tolerant Quantum Computation with Analog Quantum Error Correction

Fukui, K., Tomita, A., Okamoto, A., & Fujii, K. (2018) · Physical Review X · doi:10.1103/physrevx.8.021054 · Cited by 205

Certifying algorithms

McConnell, R. M., Mehlhorn, K., Näher, S., & Schweitzer, P. (2010) · Computer Science Review · doi:10.1016/j.cosrev.2010.09.009 · Cited by 228

The structure of claw-free graphs

Chudnovsky, M., & Seymour, P. D. (2005) · Cambridge University Press eBooks · doi:10.1017/cbo9780511734885.008 · Cited by 182

Matching structure and the matching lattice

Lovász, L. (1987) · Journal of Combinatorial Theory Series B · doi:10.1016/0095-8956(87)90021-9 · Cited by 182

Paths, Stars and the Number Three

Reed, B. A. (1996) · Combinatorics Probability Computing · doi:10.1017/s0963548300002042 · Cited by 177

Matroid matching and some applications

Lovász, L. (1980) · Journal of Combinatorial Theory Series B · doi:10.1016/0095-8956(80)90066-0 · Cited by 176

Navigating Central Path with Electrical Flows: From Flows to Matchings, and Back

Mądry, A. (2013) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2013.35 · Cited by 180

Blossom‐Quad: A non‐uniform quadrilateral mesh generator using a minimum‐cost perfect‐matching algorithm

Remacle, J., Lambrechts, J., Seny, B., Marchandise, É., Johnen, A., & Geuzainet, C. (2012) · International Journal for Numerical Methods in Engineering · doi:10.1002/nme.3279 · Cited by 172

A software methodology for compiling quantum programs

Häner, T., Steiger, D. S., Svore, K. M., & Troyer, M. (2018) · Quantum Science and Technology · doi:10.1088/2058-9565/aaa5cc · Cited by 171

On the complexity of partitioning graphs into connected subgraphs

Dyer, M., & FRIEZE, A. M. (1985) · Discrete Applied Mathematics · doi:10.1016/0166-218x(85)90008-3 · Cited by 171

On the completeness of a generalized matching problem

Kirkpatrick, D. G., & Hell, P. (1978) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/800133.804353 · Cited by 171

PyMatching: A Python Package for Decoding Quantum Codes with Minimum-Weight Perfect Matching

Higgott, O. (2022) · ACM Transactions on Quantum Computing · doi:10.1145/3505637 · Cited by 181

Reflections on graph theory

Thomassen, C. (1986) · Journal of Graph Theory · doi:10.1002/jgt.3190100308 · Cited by 170

On the ground states of the frustration model of a spin glass by a matching method of graph theory

Bieche, L., Uhry, J. P., Maynard, R., & Rammal, R. (1980) · Journal of Physics A Mathematical and General · doi:10.1088/0305-4470/13/8/005 · Cited by 170

Matchings and covers in hypergraphs

Füredi, Z. (1988) · Graphs and Combinatorics · doi:10.1007/bf01864160 · Cited by 167

An Introduction to Temporal Graphs: An Algorithmic Perspective *

Michail, O. (2016) · Internet Mathematics · doi:10.1080/15427951.2016.1177801 · Cited by 166

A primal algorithm for optimum matching

Cunningham, W. H., & Marsh, A. B. (1978) · Mathematical programming studies · doi:10.1007/bfb0121194 · Cited by 165

Fault-tolerant bosonic quantum error correction with the surface–Gottesman-Kitaev-Preskill code

Noh, K., & Chamberland, C. (2020) · Physical Review A · doi:10.1103/physreva.101.012316 · Cited by 164

On Constructing k-Connected k-Dominating Set in Wireless Networks

Dai, F., & Wu, J. (2005) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2005.302 · Cited by 163

Geometry Helps to Compare Persistence Diagrams

Kerber, M., Morozov, D., & Nigmetov, A. (2017) · ACM Journal of Experimental Algorithmics · doi:10.1145/3064175 · Cited by 160

On Linear Characterizations of Combinatorial Optimization Problems

Karp, R. M., & Papadimitriou, C. H. (1982) · SIAM Journal on Computing · doi:10.1137/0211053 · Cited by 159

Flag fault-tolerant error correction with arbitrary distance codes

Chamberland, C., & Beverland, M. E. (2018) · Quantum · doi:10.22331/q-2018-02-08-53 · Cited by 159

Efficient Data Gathering with Mobile Collectors and Space-Division Multiple Access Technique in Wireless Sensor Networks

Zhao, M., Ma, M., & Yang, Y. (2010) · IEEE Transactions on Computers · doi:10.1109/tc.2010.140 · Cited by 158

On constructing k-connected k-dominating set in wireless ad hoc and sensor networks

Dai, F., & Wu, J. (2006) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2005.12.010 · Cited by 156

Salient closed boundary extraction with ratio contour

Wang, S., Kubota, T., Siskind, J. M., & Wang, J. (2005) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2005.84 · Cited by 154

Large‐scale prediction of disulphide bridges using kernel methods, two‐dimensional recursive neural networks, and weighted graph matching

Cheng, J. J., Saigo, H., & Baldi, P. (2005) · Proteins Structure Function and Bioinformatics · doi:10.1002/prot.20787 · Cited by 155

Secure Computation

Micali, S. M., & Rogaway, P. (2007) · Springer eBooks · doi:10.1007/3-540-46766-1_32 · Cited by 153

High-Threshold Fault-Tolerant Quantum Computation with Analog Quantum Error Correction

Fukui, K., Tomita, A., Okamoto, A., & Fujii, K. (2018) · Institutional Repositories DataBase (IRDB) · Cited by 152

Algorithms for Weighted Boolean Optimization

Manquinho, V. M., Marques-Silva, J. P., & Planes, J. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-02777-2_45 · Cited by 150

Machine-learning-assisted correction of correlated qubit errors in a topological code

Baireuther, P., O’Brien, T. E., Tarasinski, B., & Beenakker, C. W. J. (2018) · Quantum · doi:10.22331/q-2018-01-29-48 · Cited by 164

Sparse blossom: correcting a million errors per core second with minimum-weight matching

Higgott, O., & Gidney, C. (2025) · Quantum · doi:10.22331/q-2025-01-20-1600 · Cited by 180

An Introduction to Temporal Graphs: An Algorithmic Perspective

Michail, O. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-24024-4_18 · Cited by 147

A theory of alternating paths and blossoms for proving correctness of the $$O(\sqrt V E)$$ general graph maximum matching algorithm

Vazirani, V. V. (1994) · COMBINATORICA · doi:10.1007/bf01305952 · Cited by 141

Surface code quantum computing by lattice surgeryPreprint

Horsman, C., Fowler, A. G., Devitt, S. J., & Meter, R. V. (2016) · Cited by 140

Facets of I-matching polyhedra

Pulleyblank, W. R., & Edmonds, J. (1974) · Lecture notes in mathematics · doi:10.1007/bfb0066196 · Cited by 136

Unlikelihood that minimal phylogenies for a realistic biological study can be constructed in reasonable computational time

Graham, R. L., & Foulds, L. R. (1982) · Mathematical Biosciences · doi:10.1016/0025-5564(82)90125-0 · Cited by 135

Distances in orientations of graphs

Chvátal, V., & Thomassen, C. (1978) · Journal of Combinatorial Theory Series B · doi:10.1016/0095-8956(78)90078-3 · Cited by 132

Fault-tolerant thresholds for quantum error correction with the surface code

Stephens, A. M. (2014) · Physical Review A · doi:10.1103/physreva.89.022321 · Cited by 133

Cell Breathing in Wireless LANs: Algorithms and Evaluation

Bahl, P., Hajiaghayi, M., Jain, K. K., Mirrokni, V., Qiu, L., & Saberi, A. (2007) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2007.20 · Cited by 129

Matching: A Well-Solved Class of Integer Linear Programs

Edmonds, J., & Johnson, E. L. (2003) · Lecture notes in computer science · doi:10.1007/3-540-36478-1_3 · Cited by 129

An $O(EV\log V)$ Algorithm for Finding a Maximal Weighted Matching in General Graphs

Galil, Z., Micali, S. M., & Gabow, H. N. (1986) · SIAM Journal on Computing · doi:10.1137/0215009 · Cited by 129

Majorana Fermion Surface Code for Universal Quantum Computation

Vijay, S., Hsieh, T. H., & Fu, L. (2015) · Physical Review X · doi:10.1103/physrevx.5.041038 · Cited by 129

Factors and factorizations of graphs—a survey

Akiyama, J., & Kanō, M. (1985) · Journal of Graph Theory · doi:10.1002/jgt.3190090103 · Cited by 128

Quantum Error Mitigation as a Universal Error Reduction Technique: Applications from the NISQ to the Fault-Tolerant Quantum Computing Eras

Suzuki, Y., Endo, S., Fujii, K., & Tokunaga, Y. (2022) · PRX Quantum · doi:10.1103/prxquantum.3.010345 · Cited by 154

Operational Research: methods and applications

Petropoulos, F., Gilbert Laporte, A., Aktaş, E., Alumur, S. A., Archetti, C., Ayhan, H., Battarra, M., Bennell, J. A., Bourjolly, J.-M., Boylan, J. E., et al. (2023) · Journal of the Operational Research Society · doi:10.1080/01605682.2023.2253852 · Cited by 161

Graph factors and factorization: 1985–2003: A survey

Plummer, M. D. (2006) · Discrete Mathematics · doi:10.1016/j.disc.2005.11.059 · Cited by 130

Brick decompositions and the matching rank of graphs

Edmonds, J., Pulleyblank, W. R., & Lovász, L. (1982) · COMBINATORICA · doi:10.1007/bf02579233 · Cited by 125

Maximum matchings in general graphs through randomization

Rabin, M. O., & Vazirani, V. V. (1989) · Journal of Algorithms · doi:10.1016/0196-6774(89)90005-9 · Cited by 125

Algorithms for the Bin Packing Problem with Conflicts

Muritiba, A. E. F., Iori, M., Malaguti, E., & Toth, P. (2009) · INFORMS journal on computing · doi:10.1287/ijoc.1090.0355 · Cited by 124

Finite-model theory - a personal perspective

Fagin, R. (1993) · Theoretical Computer Science · doi:10.1016/0304-3975(93)90218-i · Cited by 123

Decoding small surface codes with feedforward neural networks

Varsamopoulos, S., Criger, B., & Bertels, K. (2017) · Quantum Science and Technology · doi:10.1088/2058-9565/aa955a · Cited by 120

A characterization of the graphs in which the transversal number equals the matching number

Stersoul, F. (1979) · Journal of Combinatorial Theory Series B · doi:10.1016/0095-8956(79)90085-6 · Cited by 121

Universal topological phase of two-dimensional stabilizer codes

Bombín, H., Duclos-Cianci, G., & Poulin, D. (2012) · New Journal of Physics · doi:10.1088/1367-2630/14/7/073048 · Cited by 121

Frontiers in Service Science: Ride Matching for Peer-to-Peer Ride Sharing: A Review and Future Directions

Tafreshian, A., Masoud, N., & Yin, Y. (2020) · Service Science · doi:10.1287/serv.2020.0258 · Cited by 120

Minimum Edge Dominating Sets

Horton, J. D., & Kilakos, K. (1993) · SIAM Journal on Discrete Mathematics · doi:10.1137/0406030 · Cited by 120

An introduction to randomized algorithms

Karp, R. M. (1991) · Discrete Applied Mathematics · doi:10.1016/0166-218x(91)90086-c · Cited by 122

Duality Theorems for Finite Structures (Characterising Gaps and Good Characterisations)

Nešetřil, J., & Tardif, C. (2000) · Journal of Combinatorial Theory Series B · doi:10.1006/jctb.2000.1970 · Cited by 119

Fault-Tolerant Thresholds for the Surface Code in Excess of 5% Under Biased Noise

Tuckett, D. K., Bartlett, S. D., Flammia, S. T., & Brown, B. J. (2020) · Physical Review Letters · doi:10.1103/physrevlett.124.130501 · Cited by 118

A polynomial algorithm for b-matchings: An alternative approach

Anstee, R. P. (1987) · Information Processing Letters · doi:10.1016/0020-0190(87)90178-5 · Cited by 118

Minimizing maximum lateness on one machine: computational experience and some applications

Lageweg, B. J., Lenstra, J. K., & Kan, A. H. G. R. (1976) · Statistica Neerlandica · doi:10.1111/j.1467-9574.1976.tb00264.x · Cited by 114

Traveling salesman problems in temporal graphs

Michail, O., & Spirakis, P. G. (2016) · Theoretical Computer Science · doi:10.1016/j.tcs.2016.04.006 · Cited by 113

Short Cycles Make W-hard Problems Hard: FPT Algorithms for W-hard Problems in Graphs with no Short Cycles

Raman, V., & Saurabh, S. (2008) · Algorithmica · doi:10.1007/s00453-007-9148-9 · Cited by 111

Computing Maximum Flow with Augmenting Electrical Flows

Mądry, A. (2016) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2016.70 · Cited by 109

Deep Neural Network Probabilistic Decoder for Stabilizer Codes

Krastanov, S., & Jiang, L. (2017) · Scientific Reports · doi:10.1038/s41598-017-11266-1 · Cited by 123

Novel dynamic formulations for real-time ride-sharing systems

Najmi, A., Rey, D., & Rashidi, T. H. (2017) · Transportation Research Part E Logistics and Transportation Review · doi:10.1016/j.tre.2017.10.009 · Cited by 110

Maximum matchings in sparse random graphs: Karp–Sipser revisited

Aronson, J., FRIEZE, A. M., & Pittel, B. G. (1998) · Random Structures and Algorithms · doi:10.1002/(sici)1098-2418(199803)12:2 · Cited by 110

Covering, Packing and Knapsack Problems

Padberg, M. W. (1979) · Annals of discrete mathematics · doi:10.1016/s0167-5060(08)70831-8 · Cited by 110

An exact algorithm for the petrol station replenishment problem

Cornillier, F., Boctor, F. F., Gilbert Laporte, A., & Jacques Renaud, A. (2007) · Journal of the Operational Research Society · doi:10.1057/palgrave.jors.2602374 · Cited by 108

Arc routing problems: A review of the past, present, and future

Corberán, Á., Eglese, R. W., Hasle, G., Plana, I., & Sanchis, J. M. (2020) · Networks · doi:10.1002/net.21965 · Cited by 107

View-based object recognition using saliency maps

Shokoufandeh, A., Marsic, I., & Dickinson, S. (1999) · Image and Vision Computing · doi:10.1016/s0262-8856(98)00124-3 · Cited by 107

On the structure of factorizable graphs

Lovász, L. (1972) · Acta Mathematica Academiae Scientiarum Hungaricae · doi:10.1007/bf01889914 · Cited by 107

Quantum error correction for the toric code using deep reinforcement learning

Andreasson, P., Johansson, J., Liljestrand, S., & Granath, M. (2019) · Quantum · doi:10.22331/q-2019-09-02-183 · Cited by 120

On classes of relations and graphs determined by subobjects and factorobjects

Nešetřil, J., & Pultr, A. (1978) · Discrete Mathematics · doi:10.1016/0012-365x(78)90062-6 · Cited by 106

Triangular color codes on trivalent graphs with flag qubits

Chamberland, C., Kubica, A., Yoder, T. J., & Zhu, G. (2020) · New Journal of Physics · doi:10.1088/1367-2630/ab68fd · Cited by 105

A polynomial algorithm to find an independent set of maximum weight in a fork-free graph

Lozin, V., & Milanič, M. (2008) · Journal of Discrete Algorithms · doi:10.1016/j.jda.2008.04.001 · Cited by 103

Independence numbers of graphs-an extension of the Koenig-Egervary theorem

Deming, R. W. (1979) · Discrete Mathematics · doi:10.1016/0012-365x(79)90066-9 · Cited by 103

The factorization of graphs. II

Lovász, L. (1972) · Acta Mathematica Academiae Scientiarum Hungaricae · doi:10.1007/bf01889919 · Cited by 103

A n5/2 algorithm for maximum matchings in bipartite

Hopcroft, J. E., & Karp, R. M. (1971) · Annual Symposium on Switching & Automata Theory · doi:10.1109/swat.1971.1 · Cited by 103

TAHES: A Truthful Double Auction Mechanism for Heterogeneous Spectrums

Feng, X., Chen, Y., Zhang, J., Zhang, Q., & Li, B. (2012) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2012.091812.112193 · Cited by 101

Fault-Tolerant Continuous-Variable Measurement-based Quantum Computation Architecture

Larsen, M. V., Chamberland, C., Noh, K., Neergaard-Nielsen, J. S., & Andersen, U. L. (2021) · PRX Quantum · doi:10.1103/prxquantum.2.030325 · Cited by 120

Distributed Weighted Matching

Wattenhofer, M., & Wattenhofer, R. P. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-30186-8_24 · Cited by 100

Ear-decompositions of matching-covered graphs

Lovász, L. (1983) · COMBINATORICA · doi:10.1007/bf02579346 · Cited by 100

High Threshold Error Correction for the Surface Code

Wootton, J. R., & Loss, D. (2012) · Physical Review Letters · doi:10.1103/physrevlett.109.160503 · Cited by 100

A Comparison of Populations Served by Kidney Paired Donation and List Paired Donation

Gentry, S. E., Segev, D. L., & Montgomery, R. A. (2005) · American Journal of Transplantation · doi:10.1111/j.1600-6143.2005.00964.x · Cited by 100

New insights on integer-programming models for the kidney exchange problem

Constantino, M. F., Klimentova, X., Viana, A., & Rais, A. (2013) · European Journal of Operational Research · doi:10.1016/j.ejor.2013.05.025 · Cited by 100

Strategies for Scaling and Pivoting for Sparse Symmetric Indefinite Problems

Duff, I., & Pralet, S. (2005) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/04061043x · Cited by 99

Neural Belief-Propagation Decoders for Quantum Error-Correcting Codes

Liu, Y.-H., & Poulin, D. (2019) · Physical Review Letters · doi:10.1103/physrevlett.122.200501 · Cited by 95

Coping with qubit leakage in topological codes

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

The infinite sites model of genome evolution

Ma, J., Ratan, A., Raney, B. J., Suh, B. B., Miller, W., & Haussler, D. H. (2008) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0805217105 · Cited by 94

A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH

Nakamura, D., & Tamura, A. (2001) · Journal of the Operations Research Society of Japan · doi:10.15807/jorsj.44.194 · Cited by 97

Re-encoding Sequential Circuits To Reduce Power Dissipation

Hachtel, G. D., Hermida, M., Pardo, A., Poncino, M., & Somenzi, F. (1994) · International Conference on Computer Aided Design · doi:10.1109/iccad.1994.629746 · Cited by 97

Deep neural decoders for near term fault-tolerant experiments

Chamberland, C., & Ronagh, P. (2018) · Quantum Science and Technology · doi:10.1088/2058-9565/aad1f7 · Cited by 103

Successive Interference Cancellation: Carving Out MAC Layer Opportunities

Sen, S., Santhapuri, N., Choudhury, R. R., & Nelakuditi, S. (2012) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2012.17 · Cited by 95

On Reid's characterization of the ternary matroids

Bixby, R. E. (1979) · Journal of Combinatorial Theory Series B · doi:10.1016/0095-8956(79)90056-x · Cited by 94

Even Cycles in Directed Graphs

Thomassen, C. (1985) · European Journal of Combinatorics · doi:10.1016/s0195-6698(85)80025-1 · Cited by 93

Quantum Expander Codes

Leverrier, A., Tillich, J., & Zémor, G. (2015) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2015.55 · Cited by 90

Comparing Neural Network Based Decoders for the Surface Code

Varsamopoulos, S., Bertels, K., & Almudéver, C. G. (2019) · IEEE Transactions on Computers · doi:10.1109/tc.2019.2948612 · Cited by 90

Decoding color codes by projection onto surface codes

Delfosse, N. (2014) · Physical Review A · doi:10.1103/physreva.89.012317 · Cited by 90

On the complexity of some basic problems in computational convexity: I. Containment problems

Gritzmann, P., & Klee, V. L. (1994) · Discrete Mathematics · doi:10.1016/0012-365x(94)00111-u · Cited by 89

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)