Paths, Trees, and Flowers

1965/01/01 by Jack Edmonds · 62 citations
Computer Science · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Graph Theory and Algorithms

paper · pdf · doi:10.4153/cjm-1965-045-4

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 n^5/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
• 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
• Pauli Stabilizer Models for Gapped Boundaries of Twisted Quantum Doubles and Applications to Composite Dimensional Codes
• Partitioned Combinatorial Optimization Games
• 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

Related

• Maximum Matching in General Graphs Without Explicit Consideration of Blossoms Revisited
• Matchings in Geometric Graphs
• Matching complexes of trees and applications of the matching tree algorithm
• P-Matchings in Graphs: A Brief Survey with Some Open Problems
• Hierarchical b-Matching