Partial convex recolorings of trees and galled networks

DOI10.1145/2000807.2000810zbMath1295.05236OpenAlexW1991473543MaRDI QIDQ3189026

Wing-Kin Sung, Shlomo Moran, Sagi Snir

Publication date: 9 September 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2000807.2000810

zbMATH Keywords

NP-hardnessconvex recoloringpartially colored galled networkspartially colored trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

A GRASP for the convex recoloring problem in graphs ⋮ An extended formulation of the convex recoloring problem on a tree ⋮ Strong intractability results for generalized convex recoloring problems ⋮ A heuristic for the convex recoloring problem in graphs ⋮ Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems ⋮ The complexity of minimum convex coloring ⋮ Hardness and inapproximability of convex recoloring problems ⋮ The edge-recoloring cost of monochromatic and properly edge-colored paths and cycles ⋮ The convex recoloring problem: polyhedra, facets and computational experiments

This page was built for publication: Partial convex recolorings of trees and galled networks