Maximum matchings in planar graphs via Gaussian elimination
DOI10.1007/S00453-005-1187-5zbMATH Open1117.68056OpenAlexW2076736619MaRDI QIDQ2369872FDOQ2369872
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
Recommendations
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)
Cites Work
- Generalized Nested Dissection
- Applications of a Planar Separator Theorem
- Paths, Trees, and Flowers
- The Factorization of Linear Graphs
- Gaussian elimination is not optimal
- Title not available (Why is that?)
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Faster scaling algorithms for general graph matching problems
- Triangular Factorization and Inversion by Fast Matrix Multiplication
- Algorithms – ESA 2004
- Matrix multiplication via arithmetic progressions
- A Separator Theorem for Planar Graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Faster shortest-path algorithms for planar graphs
- Maximum matchings in general graphs through randomization
- Title not available (Why is that?)
- Fast and Efficient Parallel Solution of Sparse Linear Systems
- Title not available (Why is that?)
Cited In (21)
- Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle
- Unique maximum matching algorithms
- Algorithms – ESA 2004
- Computing large matchings in planar graphs with fixed minimum degree
- Computing the maximum degree of minors in mixed polynomial matrices via combinatorial relaxation
- Computing the maximum degree of minors in mixed polynomial matrices via combinatorial relaxation
- The Euclidean \(k\)-supplier problem
- Planar bus graphs
- Lozenge tilings, Glauber dynamics and macroscopic shape
- Almost exact matchings
- A simple reduction from maximum weight matching to maximum cardinality matching
- An algorithm for computing simple \(k\)-factors
- Computing large matchings in planar graphs with fixed minimum degree
- Maximum matchings in geometric intersection graphs
- A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
- Maximum 0-1 timed matching on temporal graphs
- Maximum matching in graphs with an excluded minor
- Efficient algorithms for maximum weight matchings in general graphs with small edge weights
- Simultaneously flippable edges in triangulations
- How quickly can we sample a uniform domino tiling of the \(2L\times 2L\) square via Glauber dynamics?
- Geometric stable roommates
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)
