Paths, Trees, and Flowers
1965/01/01 by Jack Edmonds · 2,366 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Artificial intelligence #Cardinality (data modeling) #Combinatorics #Computer science #Database #Discrete mathematics #Edge cover #Enhanced Data Rates for GSM Evolution #Graph #Graph Labeling and Dimension Problems #Graph Theory and Algorithms #Join (topology) #Matching (statistics) #Mathematics #Vertex (graph theory)
paper · pdf · doi:10.4153/cjm-1965-045-4
published in Canadian Journal of Mathematics 17, 449-467 (Cambridge University Press)
openalex publication_date 1965/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
Abstract
A graph G for purposes here is a finite set of elements called vertices and a finite set of elements called edges such that each edge meets exactly two vertices, called the end-points of the edge. An edge is said to join its end-points. A matching in G is a subset of its edges such that no two meet the same vertex. We describe an efficient algorithm for finding in a given graph a matching of maximum cardinality. This problem was posed and partly solved by C. Berge; see Sections 3.7 and 3.8.
Cited by
- Scaling and logic in the colour code on a superconducting quantum processor
- An Area-Efficient In-Memory Implementation Method of Arbitrary Boolean Function Based on SRAM Array
- Bargaining in a network of buyers and sellers
- Topological quantum memory
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Multiobjective Optimization for Politically Fair Districting: A Scalable Multilevel Approach
- Physics-Informed Graph-Neural Decoding of the Surface Code: the Logical Signal as an Exact Topological Pairing
- Blossom VI: A Practical Minimum Weight Perfect Matching Algorithm
- Neural Belief-Matching Decoding for Topological Quantum Error Correction Codes
- Cooperative Evolutionary Pressure and Diminishing Returns Might Explain the Fermi Paradox: On What Super-AIs Are Like
- A partition function framework for estimating logical error curves in stabilizer codes
- On the Stability of Minimum-Weight Perfect Matching on the Line
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- On the Complexity of General Graph Factor Problems
- State preservation by repetitive error detection in a superconducting quantum circuit
- An n5/2 Algorithm for Maximum Matchings in Bipartite Graphs
- Hardness of Graph-Structured Algebraic and Symbolic Problems
- Information Critical Phases under Decoherence
- Evolutionary BP+OSD Decoding for Low-Latency Quantum Error Correction
- Verifying Hadwiger's Conjecture for Examples of Graphs with α(G) = 2
- Information-efficient decoding of surface codes
- Decoding 3D color codes with boundaries
- Pinball: A Cryogenic Predecoder for Surface Code Decoding Under Circuit-Level Noise
- SAQ: Stabilizer-Aware Quantum Error Correction Decoder
- A scalable and real-time neural decoder for topological quantum codes
- Fast exact algorithms via the Matrix Tree Theorem
- Large‐scale prediction of disulphide bridges using kernel methods, two‐dimensional recursive neural networks, and weighted graph matching
- Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
- Correlation Decay for Maximum Weight Matchings on Sparse Graphs
- Robust detection of an entanglement transition in the projective transverse field Ising model
- The correlated matching decoder for the 4.8.8 color code
- Empirical Quantum Advantage in Constrained Optimization from Encoded Unitary Designs
- Forgetting Alternation and Blossoms: A New Framework for Fast Matching Augmentation and Its Applications to Sequential/Distributed/Streaming Computation
- On \k\-Roman graphs: complexity of recognition and the case of split graphs
- Decoder Switching: Breaking the Speed-Accuracy Tradeoff in Real-Time Quantum Error Correction
- Efficient magic state cultivation with lattice surgery
- Vu's conjecture holds for claw-free graphs
- Unlocking the power of partnership: How humans and machines can work together to improve face recognition
- Hierarchical Qubit-Merging Transformer for Quantum Error Correction
- 2-Factors in Graphs
- Approximate maximum likelihood decoding with K minimum weight matchings
- Efficient Post-Selection for General Quantum LDPC Codes
- Eigenvalues of Universal Covers and the Matching Polynomial
- QUASAR: Quantum Assembly Code Generation Using Tool-Augmented LLMs via Agentic RL
- A Graph Matching Based Approach for the Multi-Depot Capacitated Vehicle Routing Problem
- A decoder for the triangular color code by matching on a Möbius strip
- SQUARNA: stem maximization for accurate de novo RNA secondary structure prediction
- Fast and Accurate Decoder for the XZZX Code Using Simulated Annealing
- Localized and weighted versions of extremal problems
- Constant time enumeration of perfect bipartite matchings
- Efficient Compilation of Algorithms into Compact Linear Programs
- Coloring rings
- Boosting Sparsity in Graph Decompositions with QAOA Sampling
- Composite-Dimensional Topological Codes with Boundaries and Defects
- Partitioned Combinatorial Optimization Games
- Anchors for Homology-Based Scaffolding
- Perfect tilings with the generalised triangle in k-graphs
- On Fixed-Parameter Tractability of Weighted 0-1 Timed Matching Problem on Temporal Graphs
- Minimum-Weight Parity Factor Decoder for Quantum Error Correction
- Power and Limitations of Linear Programming Decoder for Quantum LDPC Codes
- Exact Matching in Matrix Multiplication Time
- ApproxJoin: Approximate Matching for Efficient Verification in Fuzzy Set Similarity Join
- A Programming Language for Feasible Solutions
- Entanglement-Efficient Distribution of Quantum Circuits over Large-Scale Quantum Networks
- Weighted Matching in a Poly-Streaming Model
- The even‐path problem for graphs and digraphs
- Scalable dissipative quantum error correction for qubit codes
- Perfect Matchings in Random Sparsifications of Dense Hypergraphs
- On the Importance of Studying the Membership Problem for Pedigree Polytopes
- Introduction to Quantum Error Correction with Stabilizer Codes
- Bias-tailored single-shot quantum LDPC codes
- A Refined Kernel for d-Hitting Set
- On graph automorphisms related to Snort
- Quantum Error Correction: An Introductory Guide
- Radiation-Induced Fault Detection in Superconducting Quantum Devices
- Union-Intersection Union-Find for Decoding Depolarizing Errors in Topological Codes
- Perfect tilings of 3-graphs with the generalised triangle
- Conjectured Bounds for 2-Local Hamiltonians via Token Graphs
- Self-attention U-Net decoder for toric codes
- A Ranking Framework for Network Resource Allocation and Scheduling via Hypergraphs
- Efficient AllReduce with Stragglers
- Scalable decoding protocols for fast transversal logic in the surface code
- Positive Codegree Thresholds for Perfect Matchings in Hypergraphs
- Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size
- Positive codegree thresholds for perfect matchings in hypergraphs
- The status of the P versus NP problem
- Polynomial Time Quantum Approximation Schemes for Constrained Optimisation
- High-performance local decoders for defect matching in 1D
- Optimal scheduling for two-processor systems
- Phase Transitions in Decision Problems Over Odd-Sized Alphabets
- Scalable Quantum Architecture Search via Landscape Analysis
- Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth
- Matching: A Well-Solved Class of Integer Linear Programs
- Matching is as easy as matrix inversion
- Cluster deletion and clique partitioning in graphs with bounded clique number
- Cosmological lower bound on the circuit complexity of a small problem in logic
- Edge-colouring random graphs
- Efficient Kidney Exchange: Coincidence of Wants in a Markets with Compatibility-Based Preferences
- Kidney Exchange: An Operations Perspective
- Matching, Euler tours and the Chinese postman
- Local decoder for the toric code via signal exchange
- The general maximum matching algorithm of micali and vazirani
- An O(v|v| c |E|) algoithm for finding maximum matching in general graphs
- Faster scaling algorithms for general graph matching problems
- Fast decoders for qudit topological codes
- Mitigating Classical Resource Costs in Quantum Error Correction via Generalized qLDPC Predecoding
- Designing a Million-Qubit Quantum Computer Using Resource Performance Simulator
- Optimizing glassyp-spin models
- The Nature of Computation
- Estimating decoding graphs and hypergraphs of memory QEC experiments
- Jenő Egerváry: from the origins of the Hungarian algorithm to satellite communication
- Proof of Finite Surface Code Threshold for Matching
- Simulation of rare events in quantum error correction
- Strictly local one-dimensional topological quantum error correction with symmetry-constrained cellular automata
- Graph factors and factorization: 1985–2003: A survey
- Finding long cycles in graphs
- Low-distance surface codes under realistic quantum noise
- Claw-free graphs — A survey
- On maximal independent sets of vertices in claw-free graphs
- Algorithme de recherche d'un stable de cardinalite maximum dans un graphe sans etoile
- A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
- Lifetime of topological quantum memories in thermal environment
- Line perfect graphs
- The Strong Perfect Graph Conjecture: 40 years of attempts, and its resolution
- Bottleneck extrema
- Polynomial-time perfect matchings in dense hypergraphs
- Freely Scalable Quantum Technologies Using Cells of 5-to-50 Qubits with Very Lossy and Noisy Photonic Links
- Finite-model theory - a personal perspective
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- Fault-tolerant holonomic quantum computation in surface codes
- The Complexity of Perfect Matching Problems on Dense Hypergraphs
- Polynomial-time perfect matchings in dense hypergraphs
- Tree search and quantum computation
- Universal quantum computing with twist-free and temporally encoded lattice surgery
- Quantum Proofs
- Minimum—weight perfect matching for nonintrinsic distances on the line
- Flag fault-tolerant error correction with arbitrary distance codes
- Lattice surgery-based logical state teleportation via noisy links
- NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs
- Comparison of memory thresholds for planar qudit geometries
- Improved Algorithms for Quantum MaxCut via Partially Entangled Matchings
- Machine learning for quantum matter
- Multi-path Summation for Decoding 2D Topological Codes
- Measurement-Free Topological Protection Using Dissipative Feedback
- Good characterizations for some degree constrained subgraphs
- Reinforcement learning for optimal error correction of toric codes
- Triangular color codes on trivalent graphs with flag qubits
- One-loop diagrams in the random Euclidean matching problem
- Finite-size corrections in the random assignment problem
- Path problems in skew-symmetric graphs
- Claw‐Free Graphs, Skeletal Graphs, and a Stronger Conjecture on ω, Δ, and χ
- Using bounded degree spanning trees in the design of efficient algorithms on claw-free graphs
- Domination When the Stars Are Out
- Enhanced noise resilience of the surface–Gottesman-Kitaev-Preskill code via designed bias
- Overflow-Safe Polylog-Time Parallel Minimum-Weight Perfect Matching Decoder: Toward Experimental Demonstration
- A kernel of order for vertex cover
- A 4 k 2 kernel for feedback vertex set
- Agent-Q: Fine-Tuning Large Language Models for Quantum Circuit Generation and Optimization
- Partition into cliques for cubic graphs: Planar case, complexity and approximation
- Antisymmetrical Digraphs
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- The structure of claw-free graphs
- Parallelized quantum error correction with fracton topological codes
- Claw-free graph [wikipedia]
- Hopcroft–Karp algorithm [wikipedia]
- A network approach to mixing delegates at meetings. [europepmc]
- Ancient eudicot hexaploidy meets ancestral eurosid gene order. [europepmc]
- Reconstruction of an ancestral Yersinia pestis genome and comparison with an ancient sequence. [europepmc]
- Fast Object Motion Estimation Based on Dynamic Stixels. [europepmc]
- A Ground-Based Near Infrared Camera Array System for UAV Auto-Landing in GPS-Denied Environment. [europepmc]
- Deep Neural Network Probabilistic Decoder for Stabilizer Codes. [europepmc]
- Identifying category representations for complex stimuli using discrete Markov chain Monte Carlo with people. [europepmc]
- Integrating Hi-C links with assembly graphs for chromosome-scale assembly. [europepmc]
- A cubic algorithm for the generalized rank median of three genomes. [europepmc]
- From Spin Glasses to Negative-Weight Percolation. [europepmc]
- The XZZX surface code. [europepmc]
- Continuous facility location on graphs. [europepmc]
- CHAPAO: Likelihood and hierarchical reference-based representation of biomolecular sequences and applications to compressing multiple sequence alignments. [europepmc]
- PIKAChU: a Python-based informatics kit for analysing chemical units. [europepmc]
- Surface code for low-density qubit array. [europepmc]
- Pairing Optimization via Statistics: Algebraic Structure in Pairing Problems and Its Application to Performance Enhancement. [europepmc]
- Fusion-based quantum computation. [europepmc]
- Zombie cheminformatics: extraction and conversion of Wiswesser Line Notation (WLN) from chemical documents. [europepmc]
- Scaling and logic in the colour code on a superconducting quantum processor. [europepmc]
- Lattice surgery realized on two distance-three repetition codes with superconducting qubits. [europepmc]
- Detecting genuine multipartite entanglement in multi-qubit devices with restricted measurements. [europepmc]
- Computational Biosensors: Molecules, Algorithms, and Detection Platforms [europepmc]
- Parameterized Complexity of [europepmc]
Related