A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
From MaRDI portal
Publication:1323480
DOI10.1007/BF01305952zbMath0806.05058OpenAlexW1499313444MaRDI QIDQ1323480
Publication date: 14 February 1995
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01305952
correctnesslinear time algorithmmatching algorithmtenacityblossomalternating pathssearching procedures
Search theory (90B40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
An \(O(n)\) time algorithm for maximum matching in \(P_{4}\)-tidy graphs ⋮ Gallai-Edmonds decomposition as a pruning technique ⋮ Matching numbers in fuzzy graphs ⋮ Approximating weighted matchings in parallel ⋮ Complexity results for rainbow matchings ⋮ Approximate generalized matching: \(f\)-matchings and \(f\)-edge covers ⋮ Linear-Time Approximation for Maximum Weight Matching ⋮ Graph factors and factorization: 1985--2003: a survey ⋮ Graph properties checkable in linear time in the number of vertices ⋮ On the Power of Tree-Depth for Fully Polynomial FPT Algorithms ⋮ On vertex independence number of uniform hypergraphs ⋮ Matchability and \(k\)-maximal matchings ⋮ On the parameterized vertex cover problem for graphs with perfect matching ⋮ On weighted efficient total domination ⋮ Online sum-paintability: the slow-coloring game ⋮ Variations of maximum-clique transversal sets on graphs ⋮ (1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings ⋮ Maximum matching in regular and almost regular graphs ⋮ Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems ⋮ A simple reduction from maximum weight matching to maximum cardinality matching ⋮ The complexity of König subgraph problems and above-guarantee vertex cover ⋮ Efficiently hex-meshing things with topology ⋮ The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number ⋮ Extracting constrained 2-interval subsets in 2-interval sets ⋮ Edge $k$-$q$-Colorability of Graphs ⋮ Affine-invariant strictly cyclic Steiner quadruple systems ⋮ A polynomial algorithm to find an independent set of maximum weight in a fork-free graph ⋮ Unnamed Item ⋮ A combinatoric interpretation of dual variables for weighted matching and \(f\)-factors ⋮ On the anti-Kekulé problem of cubic graphs ⋮ A simple approximation algorithm for the weighted matching problem ⋮ On the Complexity of Computing the Excessive [B-Index of a Graph] ⋮ Unnamed Item ⋮ Linear-time parameterized algorithms with limited local resources ⋮ Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases ⋮ Length-constrained path-matchings in graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A linear-time algorithm for a special case of disjoint set union
- A \(0(| V | \cdot | E |)\) algorithm for maximum matching of graphs
- TWO THEOREMS IN GRAPH THEORY
- Efficiency of a Good But Not Linear Set Union Algorithm
- An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
- Paths, Trees, and Flowers
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
