Color spanning objects: algorithms and hardness results

DOI10.1007/978-3-319-29221-2_4MaRDI QIDQ2795933zbMATH OpenOpenAlexFDO

Authors Sandip Banerjee, Neeldhara Misra, Subhas C. Nandy

Publication date 23 March 2016

Published in Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-29221-2_4

zbMATH Keywords

color spanning setscomputational geometryexact algorithmsparameterized complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Nonnumerical algorithms (68W05)

Recommendations

• Color spanning objects: algorithms and hardness results
• Shortest color-spanning intervals
• Shortest color-spanning intervals
• On some geometric problems of color-spanning sets
• On some geometric problems of color-spanning sets

Cites work

• A kernelization algorithm for \(d\)-hitting set
• Algorithms for interval structures with applications
• Computing the smallest color-spanning axis-parallel square
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Incompressibility through Colors and IDs
• Shortest color-spanning intervals
• SMALLEST COLOR-SPANNING OBJECT REVISITED
• Smallest color-spanning objects
• The upper envelope of Voronoi surfaces and its applications
• Voronoi diagram for services neighboring a highway

Cited in

(7)

• Selecting and covering colored points
• Color-spanning localized query
• Color spanning objects: algorithms and hardness results
• Shortest color-spanning intervals
• NP-Completeness of Spreading Colored Points
• Smallest color-spanning objects
• Shortest color-spanning intervals

This page was built for publication: Color spanning objects: algorithms and hardness results

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