Computing large matchings fast

DOI10.1145/1868237.1868238MaRDI QIDQ3188982zbMATH OpenOpenAlexFDO

Authors Ignaz Rutter, Alexander Wolff

Publication date 9 September 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://publikationen.bibliothek.kit.edu/1000007350

zbMATH Keywords

maximum matchings3-connected planar graphs3-regular graphslarge matchingsbounded-degree block treesmaxdeg-3 graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Computing large matchings in planar graphs with fixed minimum degree
• Computing large matchings in planar graphs with fixed minimum degree
• Maximum matching in regular and almost regular graphs
• Finding maximum matchings in random regular graphs in linear expected time
• Perfect matchings in \(\tilde{O}(n^{1.5})\) time in regular bipartite graphs

Cited in

(11)

• Fast profile matching algorithms - A survey
• Solving (large scale) matching problems combinatorially
• Computing large matchings in planar graphs with fixed minimum degree
• Solving large-scale matching problems efficiently: A new primal matching approach
• Edge guards for polyhedra in three-space
• Linear reductions of maximum matching
• Maximum matching in regular and almost regular graphs
• Computing large matchings in planar graphs with fixed minimum degree
• scientific article; zbMATH DE number 1003267 (Why is no real title available?)
• Lazy or eager dynamic matching may not be fast
• On adaptive algorithms for maximum matching

This page was built for publication: Computing large matchings fast

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3188982)