Maximum matchings in planar graphs via Gaussian elimination

DOI10.1007/S00453-005-1187-5MaRDI QIDQ2369872zbMATH OpenOpenAlexFDO

Authors Marcin Mucha, Piotr Sankowski

Publication date 21 June 2007

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-005-1187-5

Mathematics Subject Classification ID

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

Recommendations

• Algorithms – ESA 2004
• Maximum matching in graphs with an excluded minor
• Maximum matchings in general graphs through randomization
• scientific article; zbMATH DE number 3965443
• Computing large matchings in planar graphs with fixed minimum degree

Cites work

• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• scientific article; zbMATH DE number 3698383 (Why is no real title available?)
• scientific article; zbMATH DE number 177842 (Why is no real title available?)
• scientific article; zbMATH DE number 6472600 (Why is no real title available?)
• scientific article; zbMATH DE number 3321957 (Why is no real title available?)
• A Separator Theorem for Planar Graphs
• Algorithms – ESA 2004
• Applications of a Planar Separator Theorem
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Fast and Efficient Parallel Solution of Sparse Linear Systems
• Faster scaling algorithms for general graph matching problems
• Faster shortest-path algorithms for planar graphs
• Gaussian elimination is not optimal
• Generalized Nested Dissection
• Matrix multiplication via arithmetic progressions
• Maximum matchings in general graphs through randomization
• Paths, Trees, and Flowers
• The Factorization of Linear Graphs
• Triangular Factorization and Inversion by Fast Matrix Multiplication

Cited in

(21)

• Computing the maximum degree of minors in mixed polynomial matrices via combinatorial relaxation
• The Euclidean \(k\)-supplier problem
• Computing the maximum degree of minors in mixed polynomial matrices via combinatorial relaxation
• Computing large matchings in planar graphs with fixed minimum degree
• Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle
• Algorithms – ESA 2004
• A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
• An algorithm for computing simple \(k\)-factors
• Planar bus graphs
• Efficient algorithms for maximum weight matchings in general graphs with small edge weights
• Almost exact matchings
• Unique maximum matching algorithms
• How quickly can we sample a uniform domino tiling of the \(2L\times 2L\) square via Glauber dynamics?
• Simultaneously flippable edges in triangulations
• Maximum matchings in geometric intersection graphs
• Lozenge tilings, Glauber dynamics and macroscopic shape
• Geometric stable roommates
• Computing large matchings in planar graphs with fixed minimum degree
• Maximum 0-1 timed matching on temporal graphs
• A simple reduction from maximum weight matching to maximum cardinality matching
• Maximum matching in graphs with an excluded minor

This page was built for publication: Maximum matchings in planar graphs via Gaussian elimination

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