Abstract
Given points in the plane, it is well-known that there always exists a perfect straight-line non-crossing matching. We show that it is -complete to decide if a partial matching can be augmented to a perfect one, via a reduction from 1-in-3-SAT. This result also holds for bichromatic matchings.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.