Unique Maximum Matching Algorithms

DOI10.1006/jagm.2001.1167zbMath0982.05094OpenAlexW2076062247MaRDI QIDQ2746432

Harold N. Gabow, Haim Kaplan, Robert Endre Tarjan

Publication date: 8 April 2002

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/72b3e75937ea669c11530e49461169ec38b300dc

zbMATH Keywords

planar graphsdepth-first searchperfect matching\(f\)-factormaximum matchingsKotzig's theoremblossom-shrinking algorithmdynamic connectivity algorithm

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

Computing unique maximum matchings in \(O(m)\) time for König-Egerváry graphs and unicyclic graphs ⋮ Graph factors and factorization: 1985--2003: a survey ⋮ Unnamed Item ⋮ Are unique subgraphs not easier to find? ⋮ Maximum matchings in scale-free networks with identical degree distribution ⋮ Computing large matchings in planar graphs with fixed minimum degree ⋮ On some graphs with a unique perfect matching ⋮ On the König deficiency of zero-reducible graphs ⋮ VERY WELL-COVERED GRAPHS OF GIRTH AT LEAST FOUR AND LOCAL MAXIMUM STABLE SET GREEDOIDS ⋮ Contracting a Planar Graph Efficiently ⋮ Unique subgraphs are not easier to find

This page was built for publication: Unique Maximum Matching Algorithms