Maximum matching in regular and almost regular graphs

DOI10.1007/s00453-012-9625-7zbMath1263.05081OpenAlexW2108763491MaRDI QIDQ1949755

Raphael Yuster

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

zbMATH Keywords

algorithmmaximum matchingregular graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (12)

A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs ⋮ The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes ⋮ Maximum matchings and minimum dominating sets in Apollonian networks and extended tower of Hanoi graphs ⋮ On vertex independence number of uniform hypergraphs ⋮ COMBINATORIAL PROPERTIES FOR A CLASS OF SIMPLICIAL COMPLEXES EXTENDED FROM PSEUDO-FRACTAL SCALE-FREE WEB ⋮ The power of linear-time data reduction for maximum matching ⋮ The \(b\)-\textsc{Matching} problem in distance-hereditary graphs and beyond ⋮ Maximum matchings in scale-free networks with identical degree distribution ⋮ Unnamed Item ⋮ The Power of Linear-Time Data Reduction for Maximum Matching ⋮ Combinatorial properties of Farey graphs ⋮ Maximum matching in almost linear time on graphs of bounded clique-width

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• 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

This page was built for publication: Maximum matching in regular and almost regular graphs