Planarizing Gadgets for Perfect Matching Do Not Exist

Planarizing Gadgets for Perfect Matching Do Not Exist
复制标题

DOI：
10.1145/2934310
复制
发表时间：
2012-08
期刊：
ACM Transactions on Computation Theory (TOCT)
影响因子：
--
通讯作者：
R. Gurjar;A. Korwar;J. Messner;Simon Straub;T. Thierauf
R. Gurjar;A. Korwar;J. Messner;Simon Straub;T. Thierauf
中科院分区：
其他
文献类型：
--
作者：
R. Gurjar;A. Korwar;J. Messner;Simon Straub;T. Thierauf

文献摘要

被引文献

相似文献

为了将图形问题简化为平面问题，标准技术是通过平面化小工具来替换输入图形的绘制中的交叉。我们无条件地表明，这样的减少是不可能的完美匹配的问题，也扩展到其他一些问题的完美匹配。我们进一步表明，没有平坦化的小工具的哈密顿循环问题。
To reduce a graph problem to its planar version, a standard technique is to replace crossings in a drawing of the input graph by planarizing gadgets. We show unconditionally that such a reduction is not possible for the perfect matching problem and also extend this to some other problems related to perfect matching. We further show that there is no planarizing gadget for the Hamiltonian cycle problem.