Planarizing Gadgets for Perfect Matching Do Not Exist

DOI10.1007/978-3-642-32589-2_43MaRDI QIDQ2912747zbMATH OpenOpenAlexFDO

Authors Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf

Publication date 25 September 2012

Published in Mathematical Foundations of Computer Science 2012 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-32589-2_43

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Planarizing gadgets for perfect matching do not exist
• Generalized planar matching
• Revisiting a cutting-plane method for perfect matchings
• scientific article; zbMATH DE number 2079389
• A matching problem in the plane
• Matching planar maps
• Bottleneck matching in the plane
• Planar matching in streams revisited
• Perfect matching on regular polyhedra
• On a matching problem in the plane

Cited in

(7)

• On the construction of graphs with a planar bipartite double cover from Boolean formulas and its application to counting satisfying solutions
• Planarizing gadgets for perfect matching do not exist
• A weighted perfect matching with constraints on weights of its parts
• On the exact matching problem in dense graphs
• Exact matching: correct parity and FPT parameterized by independence number
• Computing balanced solutions for large international kidney exchange schemes when cycle length is unbounded
• On finding -th smallest perfect matchings

This page was built for publication: Planarizing Gadgets for Perfect Matching Do Not Exist

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