Perfect matching for biconnected cubic graphs in O(n ^2 n) time

DOI10.1007/978-3-642-11266-9_27MaRDI QIDQ3401102zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Krzysztof Diks, Piotr Stanczyk

Publication date 28 January 2010

Published in SOFSEM 2010: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-11266-9_27

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Nonnumerical algorithms (68W05)

Recommendations

• Perfect matchings in \(\tilde{O}(n^{1.5})\) time in regular bipartite graphs
• Linear reductions of maximum matching
• Perfect matchings via uniform sampling in regular bipartite graphs
• Minimum maximal matchings in cubic graphs
• Perfect matchings in O(n n) time in regular bipartite graphs

Cited in

(10)

• A fast algorithm for computing irreducible triangulations of closed surfaces in \(\mathbb{E}^d\)
• Representing graphs and hypergraphs by touching polygons in 3D
• Linear reductions of maximum matching
• The cost of perfection for matchings in graphs
• Edge k-q-colorability of graphs
• Affine-invariant strictly cyclic Steiner quadruple systems
• Approximate cycle double cover
• Finding perfect matchings in bridgeless cubic multigraphs without dynamic (2-)connectivity
• On the time complexity of finding a well-spread perfect matching in bridgeless cubic graphs
• Linear algorithm for selecting an almost regular spanning subgraph in an almost regular graph

This page was built for publication: Perfect matching for biconnected cubic graphs in \(O(n \log ^{2} n)\) time

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