Computing minimum diameter color-spanning sets is hard

DOI10.1016/J.IPL.2011.07.015MaRDI QIDQ1944200zbMATH OpenOpenAlexFDO

Authors Rudolf Fleischer, Xiaoming Xu

Publication date 4 April 2013

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2011.07.015

zbMATH Keywords

analysis of algorithmsNP hardnessminimum diameter color-spanning disk

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites work

• scientific article; zbMATH DE number 1875422 (Why is no real title available?)
• Computing minimum diameter color-spanning sets
• On some geometric problems of color-spanning sets

Cited in

(14)

• Online \(k\)-color spanning disk problems
• On the fixed-parameter tractability of some matching problems under the color-spanning model
• Shortest color-spanning intervals
• On some matching problems under the color-spanning model
• The 2-mixed-center color spanning problem
• A fully polynomial time approximation scheme for the smallest diameter of imprecise points
• Rainbow polygons for colored point sets in the plane
• On approximability of minimum color-spanning ball in high dimensions
• Minimum color spanning circle of imprecise points
• On the \(k\)-colored rainbow sets in fixed dimensions
• The approximation algorithms for a class of multiple-choice problem
• Minimum color spanning circle in imprecise setup
• Approximation algorithms for color spanning diameter
• Computing largest minimum color-spanning intervals of imprecise points

This page was built for publication: Computing minimum diameter color-spanning sets is hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1944200)