Advertisement
Published in:
2010 | OriginalPaper | Chapter
NP-Completeness of Spreading Colored Points
Authors : Ovidiu Daescu, Wenqi Ju, Jun Luo
Published in: Combinatorial Optimization and Applications
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
There are
n
points in the plane and each point is painted by one of
m
colors where
m
≤
n
. We want to select
m
different color points such that (1) the total edge length of resulting minimal spanning tree is as small as possible; or (2) the total edge length of resulting minimal spanning tree is as large as possible; or (3) the perimeter of the convex hull of
m
different color points is as small as possible. We prove NP-completeness for those three problems and give approximations algorithms for the third problem.