Veröffentlichung

Titel:
The Partition Spanning Forest Problem
AutorInnen:
Philipp Kindermann
Boris Klemz
Ignaz Rutter
Patrick Schnider
André Schulz
Kategorie:
Workshopbeiträge
erschienen in:
Proc. 34th European Workshop on Computational Geometry (EuroCG'18). To appear.
Abstract:

Given a set of colored points in the plane, we ask if there exists a crossing-free straight-line drawing of a spanning forest, such that every tree in the forest contains exactly the points of one color class. We show that the problem is NP-complete, even if every color class contains at most five points, but it is solvable in O(n2) time when each color class contains at most three points. If we require that the spanning forest is a linear forest, then the problem becomes NP-complete even if every color class contains at most four points.

BibTeX-Eintrag:
@InProceedings{kkrss-tpsfp-eurocg18, author = {Philipp Kindermann and Boris Klemz and Ignaz Rutter and Patrick Schnider and Andr{\'e} Schulz}, title = {The Partition Spanning Forest Problem}, booktitle = {Proc. 34th European Workshop on Computational Geometry (EuroCG'18)}, year = {2018}, editor = {Wolfgang Mulzer}, publisher = {Berlin}, note = {To appear.}, abstract = {Given a set of colored points in the plane, we ask if there exists a crossing-free straight-line drawing of a spanning forest, such that every tree in the forest contains exactly the points of one color class. We show that the problem is NP-complete, even if every color class contains at most five points, but it is solvable in $O(n^2)$ time when each color class contains at most three points. If we require that the spanning forest is a linear forest, then the problem becomes NP-complete even if every color class contains at most four points.}, }
Philipp Kindermann | 20.09.2018