Computing large matchings in planar graphs with fixed minimum degree

DOI10.1016/J.TCS.2010.06.012MaRDI QIDQ553342zbMATH OpenOpenAlexFDO

Authors Robert Franke, Ignaz Rutter, Dorothea Wagner

Publication date 27 July 2011

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

large matchinglinear-timemindeg-3 graphplanar graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40)

Recommendations

• Computing large matchings in planar graphs with fixed minimum degree
• Computing large matchings fast
• Maximum matchings in planar graphs via Gaussian elimination
• Algorithms – ESA 2004
• Maximum matching in graphs with an excluded minor

Cites work

• A linear algorithm for perfect matching in hexagonal systems
• Bipartite Edge Coloring in O(\Delta m) Time
• Computing large matchings fast
• Conway's Tiling Groups
• Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
• Efficient algorithms for Petersen's matching theorem
• Flow in Planar Graphs with Multiple Sources and Sinks
• scientific article; zbMATH DE number 5764781 (Why is no real title available?)
• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• Lower bounds on the cardinality of the maximum matchings of planar graphs
• Matching for Graphs of Bounded Degree
• Matching theory
• Matrix multiplication via arithmetic progressions
• Maximum matching in graphs with an excluded minor
• Maximum matchings in planar graphs via Gaussian elimination
• On Representatives of Subsets
• Perfect matchings in the triangular lattice
• Planar graphs, negative weight edges, shortest paths, and near linear time
• The Factorization of Linear Graphs
• Tight bounds on maximal and maximum matchings
• Unique maximum matching algorithms

Cited in

(9)

• On the A_-spectral radius of graphs without large matchings
• Computing large matchings fast
• Computing large matchings in planar graphs with fixed minimum degree
• Space-efficient approximation scheme for maximum matching in sparse graphs
• On the Size of Matchings in 1-Planar Graph with High Minimum Degree
• Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
• Matchings in 1‐planar graphs with large minimum degree
• A Hall-type theorem with algorithmic consequences in planar graphs
• Large matchings in maximal 1-planar graphs

Describes a project that uses

Uses Software

• Boost
• BGL

This page was built for publication: Computing large matchings in planar graphs with fixed minimum degree

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