Planarizing Gadgets for Perfect Matching Do Not Exist

DOI10.1007/978-3-642-32589-2_43zbMath1365.05280OpenAlexW1819297031MaRDI QIDQ2912747

Rohit Gurjar, Simon Straub, Arpita Korwar, Jochen Messner, 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

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) 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 (2)

A weighted perfect matching with constraints on weights of its parts ⋮ On the construction of graphs with a planar bipartite double cover from Boolean formulas and its application to counting satisfying solutions

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