Computing large matchings in planar graphs with fixed minimum degree

DOI10.1016/j.tcs.2010.06.012zbMath1217.68250OpenAlexW1964708784MaRDI QIDQ553342

Ignaz Rutter, Dorothea Wagner, Robert Franke

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

planar graphlinear-timelarge matchingmindeg-3 graph

Mathematics Subject Classification ID

Analysis of algorithms (68W40) 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)

Related Items

On the \(A_\alpha\)-spectral radius of graphs without large matchings

Uses Software

• Boost
• BGL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
• Matrix multiplication via arithmetic progressions
• Matching theory
• Lower bounds on the cardinality of the maximum matchings of planar graphs
• A linear algorithm for perfect matching in hexagonal systems
• Tight bounds on maximal and maximum matchings
• Perfect matchings in the triangular lattice
• Maximum matchings in planar graphs via Gaussian elimination
• Planar graphs, negative weight edges, shortest paths, and near linear time
• Efficient Algorithms for Petersen's Matching Theorem
• Unique Maximum Matching Algorithms
• Computing large matchings fast
• Conway's Tiling Groups
• Matching for Graphs of Bounded Degree
• Bipartite Edge Coloring in $O(\Delta m)$ Time
• On Representatives of Subsets
• Flow in Planar Graphs with Multiple Sources and Sinks
• The Factorization of Linear Graphs

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