Minimum diameter color-spanning sets revisited☆

Add time:09/03/2019    Source:sciencedirect.com

We address point sets in the d-dimensional space, in which every point is colored with at least one color out of the set C. A Color-Spanning Set or Rainbow Set is a set of points that covers all colors of C. The diameter of a set is the maximum distance between two points in the set. In this paper we answer some open questions about Minimum Diameter Color-Spanning Sets in d-dimensional space, which were studied by Fleischer and Xu (2010), and extend this concept to general graphs. We show that the problem is W[1] hard for parameter |C| and not in PTAS if the number of dimensions is part of the input. Furthermore we demonstrate the membership in W[2]. Most importantly we present two exact solution methods, which both can also be used for the Largest Closest Color-Spanning Set Problem and compare them in an experimental evaluation. For general graphs we show that Minimum Diameter Color-Spanning Set Problem is NP-hard and W[1]-hard for parameter |C| but give a polynomial time algorithm for trees. In addition we develop a polynomial time 2-approximation algorithm for general graphs and prove that this problem admits no better approximation factor, unless P=NP.

We also recommend Trading Suppliers and Manufacturers of Span 20 (cas 1338-39-2). Pls Click Website Link as below: cas 1338-39-2 suppliers

Prev:Constructing spanning trees in augmented cubes
Next:Almost disjoint spanning trees: Relaxing the conditions for completely independent spanning trees)