Connected Coloring Completion for General Graphs: Algorithms and Complexity
From MaRDI portal
Publication:3608833
DOI10.1007/978-3-540-73545-8_10zbMath1206.05040OpenAlexW1577433976MaRDI QIDQ3608833
Sagi Snir, Igor Razgon, Michael R. Fellows, Benny Chor, Frances A. Rosamond, Mark A. Ragan
Publication date: 6 March 2009
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-73545-8_10
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Problems related to evolution (92D15) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (17)
A \(2^{O(k)}\)poly\((n)\) algorithm for the parameterized convex recoloring problem ⋮ Convex Recoloring Revisited: Complexity and Exact Algorithms ⋮ An extended formulation of the convex recoloring problem on a tree ⋮ Strong intractability of generalized convex recoloring problems ⋮ 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 ⋮ Parameterized complexity of finding small degree-constrained subgraphs ⋮ The complexity of minimum convex coloring ⋮ On the complexity of some colorful problems parameterized by treewidth ⋮ A Survey on the Complexity of Flood-Filling Games ⋮ Hardness and inapproximability of convex recoloring problems ⋮ Convex recoloring of paths ⋮ Upper and lower bounds for finding connected motifs in vertex-colored graphs ⋮ Convex Recoloring of Paths ⋮ Tractability and hardness of flood-filling games on trees ⋮ The convex recoloring problem: polyhedra, facets and computational experiments
This page was built for publication: Connected Coloring Completion for General Graphs: Algorithms and Complexity
