Author | Conference | Journal | Organization | Year | DOI
Look for results that meet for the following criteria:
Academic
Publications
Computing Minimum Diameter Color-Spanning Sets
Edit
Computing Minimum Diameter Color-Spanning Sets   (Citations: 3)
BibTex | RIS | RefWorks Download
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  ∞  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.
Conference: Frontiers in Algorithmics - FAW , pp. 285-292, 2010
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Fleischer and Xu [11] gave polynomial time algorithms for finding a minimum diameter color-spanning set using the L1 or L∞ metric and proved that the problem is NP-hard for all Lp with 1 <p< ∞. They also provided an O(1)-approximation algorithm for Algorithms for Interval Structures with Applications 199...

    Danny Z. Chen, et al. Algorithms for Interval Structures with Applications

Order by:

Citations (3)

Share this on | Contribute to Academic