Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1145/2934310 | TOCT |
Keywords | DocType | Volume |
planarizing gadget,standard technique,planar version,perfect matching problem,perfect matching,graph problem,hamiltonian cycle problem,input graph | Journal | 8 |
Issue | ISSN | Citations |
4 | 1942-3454 | 0 |
PageRank | References | Authors |
0.34 | 21 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rohit Gurjar | 1 | 38 | 6.80 |
| Arpita Korwar | 2 | 29 | 3.60 |
| Jochen Messner | 3 | 70 | 4.86 |
| Simon Straub | 4 | 0 | 0.34 |
| Thomas Thierauf | 5 | 288 | 33.59 |