Generalized Planar Matching
In this paper, we prove that maximum planar H-matching (the problem of determining the maximum number of node-disjointed copies of the fixed graph H contained in a variable planar graph G) is NP-complete for any connected planar graph H with three or more nodes. We also show that perfect planar H-ma...
| Main Authors: | , , , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149083 |
| _version_ | 1826213032425947136 |
|---|---|
| author | Berman, Fran Leighton, Tom Shor, Peter Snyder, Larry |
| author_facet | Berman, Fran Leighton, Tom Shor, Peter Snyder, Larry |
| author_sort | Berman, Fran |
| collection | MIT |
| description | In this paper, we prove that maximum planar H-matching (the problem of determining the maximum number of node-disjointed copies of the fixed graph H contained in a variable planar graph G) is NP-complete for any connected planar graph H with three or more nodes. We also show that perfect planar H-matching is NP-complete for any connected outerplanar graph H with three or more nodes, and is, somewhat surprisingly, solvable in linear time for triangulated H with four or more nodes. The results generalize and unify several special-case results proved in the literature. The techniques can also be applied to solve a variety of problems, including the optimal tile salvage problem from wafer-scale integration. Although we prove that the optimal tile salvage problem and other like it are NP-complete, we also describe provably good approximation algorithms that are suitable for practical applications. |
| first_indexed | 2024-09-23T15:42:15Z |
| id | mit-1721.1/149083 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T15:42:15Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1490832023-03-30T03:12:26Z Generalized Planar Matching Berman, Fran Leighton, Tom Shor, Peter Snyder, Larry In this paper, we prove that maximum planar H-matching (the problem of determining the maximum number of node-disjointed copies of the fixed graph H contained in a variable planar graph G) is NP-complete for any connected planar graph H with three or more nodes. We also show that perfect planar H-matching is NP-complete for any connected outerplanar graph H with three or more nodes, and is, somewhat surprisingly, solvable in linear time for triangulated H with four or more nodes. The results generalize and unify several special-case results proved in the literature. The techniques can also be applied to solve a variety of problems, including the optimal tile salvage problem from wafer-scale integration. Although we prove that the optimal tile salvage problem and other like it are NP-complete, we also describe provably good approximation algorithms that are suitable for practical applications. 2023-03-29T14:25:41Z 2023-03-29T14:25:41Z 1985-04 https://hdl.handle.net/1721.1/149083 14701092 MIT-LCS-TM-273 application/pdf |
| spellingShingle | Berman, Fran Leighton, Tom Shor, Peter Snyder, Larry Generalized Planar Matching |
| title | Generalized Planar Matching |
| title_full | Generalized Planar Matching |
| title_fullStr | Generalized Planar Matching |
| title_full_unstemmed | Generalized Planar Matching |
| title_short | Generalized Planar Matching |
| title_sort | generalized planar matching |
| url | https://hdl.handle.net/1721.1/149083 |
| work_keys_str_mv | AT bermanfran generalizedplanarmatching AT leightontom generalizedplanarmatching AT shorpeter generalizedplanarmatching AT snyderlarry generalizedplanarmatching |