Maximum matching in regular and almost regular graphs
From MaRDI portal
Publication:1949755
DOI10.1007/s00453-012-9625-7zbMath1263.05081MaRDI QIDQ1949755
Publication date: 16 May 2013
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-012-9625-7
05C35: Extremal problems in graph theory
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs, Unnamed Item, The Power of Linear-Time Data Reduction for Maximum Matching, COMBINATORIAL PROPERTIES FOR A CLASS OF SIMPLICIAL COMPLEXES EXTENDED FROM PSEUDO-FRACTAL SCALE-FREE WEB, On vertex independence number of uniform hypergraphs, Maximum matchings in scale-free networks with identical degree distribution, Maximum matchings and minimum dominating sets in Apollonian networks and extended tower of Hanoi graphs, Maximum matching in almost linear time on graphs of bounded clique-width, The power of linear-time data reduction for maximum matching, The \(b\)-\textsc{Matching} problem in distance-hereditary graphs and beyond, Combinatorial properties of Farey graphs, The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes
Cites Work
- Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
- A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
- Perfect matchings in o( n log n ) time in regular bipartite graphs
- Perfect matchings via uniform sampling in regular bipartite graphs
- Algorithms for Edge Coloring Bipartite Graphs and Multigraphs
- Faster scaling algorithms for general graph matching problems
- Paths, Trees, and Flowers
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
