Shortest color-spanning intervals

DOI10.1016/J.TCS.2015.01.039MaRDI QIDQ896153zbMATH OpenOpenAlexFDO

Authors Haitao Wang, Minghui Jiang

Publication date 11 December 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.01.039

zbMATH Keywords

computational geometryexact algorithmsparameterized complexitycolor-spanning objects

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Shortest color-spanning intervals
• Color spanning objects: algorithms and hardness results
• Color spanning objects: algorithms and hardness results
• On the \(k\)-coloring of intervals
• Algorithms for interval structures with applications

Cites work

• scientific article; zbMATH DE number 1875422 (Why is no real title available?)
• Algorithms for interval structures with applications
• Computing minimum diameter color-spanning sets
• Computing minimum diameter color-spanning sets is hard
• Computing the smallest color-spanning axis-parallel square
• Dominating set is fixed parameter tractable in claw-free graphs
• On some geometric problems of color-spanning sets
• On the parameterized complexity of multiple-interval graph problems
• Representing a functional curve by curves with fewer peaks
• SMALLEST COLOR-SPANNING OBJECT REVISITED
• Tight approximation bounds for connectivity with a color-spanning set

Cited in

(9)

• Color-spanning localized query
• Efficiently approximating color-spanning balls
• Algorithms for interval structures with applications
• Color spanning objects: algorithms and hardness results
• Shortest color-spanning intervals
• Minimum color spanning circle of imprecise points
• The approximation algorithms for a class of multiple-choice problem
• Color spanning objects: algorithms and hardness results
• Algorithms for interval structures with applications

This page was built for publication: Shortest color-spanning intervals

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