NP-Completeness of Spreading Colored Points

DOI10.1007/978-3-642-17458-2_5MaRDI QIDQ3066143zbMATH OpenOpenAlexFDO

Authors Ovidiu Daescu, Wenqi Ju, Jun Luo

Publication date 8 January 2011

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-17458-2_5

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Computing methodologies for image processing (68U10) Approximation algorithms (68W25)

Recommendations

• Color spanning objects: algorithms and hardness results
• Color spanning objects: algorithms and hardness results
• NP-completeness of local colorings of graphs
• The complexity of nonrepetitive coloring
• A Complexity Dichotomy for the Coloring of Sparse Graphs
• Near-colorings: non-colorable graphs and NP-completeness
• The complexity of colouring problems on dense graphs
• NP-completeness of edge-colouring some restricted graphs
• The complexity of some graph colouring problems
• Colouring, constraint satisfaction, and complexity

Cited in

(10)

• Selecting and covering colored points
• Largest and smallest area triangles on imprecise points
• Minimum color spanning circle of imprecise points
• Computing shortest heterochromatic monotone routes
• Minimum color spanning circle in imprecise setup
• Algorithms for interval structures with applications
• Algorithms for interval structures with applications
• New results on stabbing segments with a polygon
• New results on the coarseness of bicolored point sets
• Largest convex hulls for convex-hull disjoint clusters with bounded size

This page was built for publication: NP-Completeness of Spreading Colored Points

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