Computing Minimum Diameter Color-Spanning Sets

Computing Minimum Diameter Color-Spanning Sets
复制标题

DOI：
10.1007/978-3-642-14553-7_27
复制
发表时间：
2010-08
期刊：
--
影响因子：
--
通讯作者：
R. Fleischer;Xiaoming Xu
R. Fleischer;Xiaoming Xu
中科院分区：
其他
文献类型：
--
作者：
R. Fleischer;Xiaoming Xu

文献摘要

被引文献

相似文献

我们研究了最近在数据库界引起了一些关注的最小直径颜色生成集问题。我们证明了这个问题对于L1和L ∞度量都可以在多项式时间内得到解决，而对于其他所有的Lp度量，即使在二维空间中，这个问题也是NP-难的.然而，我们可以有效地计算常数因子近似。
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 forL1andL∞metrics, while it is NP-hard for all otherLpmetrics even in two dimensions. However, we can efficiently compute a constant factor approximation.