Computing minimum diameter color-spanning sets. (English) Zbl 1288.68115

Lee, Der-Tsai (ed.) et al., Frontiers in algorithmics. 4th international workshop, FAW 2010, Wuhan, China, August 11–13, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-14552-0/pbk). Lecture Notes in Computer Science 6213, 285-292 (2010).
Summary: We study the minimum diameter color-spanning set problem which has recently drawn some attention in the database community. We show that the problem can be solved in polynomial time for \(L _{1}\) and \(L _{ \infty }\) metrics, while it is NP-hard for all other \(L _{p }\) metrics even in two dimensions. However, we can efficiently compute a constant factor approximation.
For the entire collection see [Zbl 1194.68052].


68Q25 Analysis of algorithms and problem complexity
05C15 Coloring of graphs and hypergraphs
68W25 Approximation algorithms
Full Text: DOI