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)

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²) 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.

Download:

arXiv

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.}, }