Connected Coloring Completion for General Graphs: Algorithms and Complexity

DOI10.1007/978-3-540-73545-8_10MaRDI QIDQ3608833zbMATH OpenOpenAlexFDO

Authors Benny Chor, Michael R. Fellows, Mark A. Ragan, Igor Razgon, Frances Rosamond, Sagi Snir

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

zbMATH Keywords

bioinformaticsalgorithms and complexity

Mathematics Subject Classification ID

Problems related to evolution (92D15) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Strong intractability results for generalized convex recoloring problems
• Strong intractability of generalized convex recoloring problems
• On the parameterized complexity of colorful components and related problems

Cited in

(17)

• The convex recoloring problem: polyhedra, facets and computational experiments
• The complexity of minimum convex coloring
• Convex Recoloring Revisited: Complexity and Exact Algorithms
• A Survey on the Complexity of Flood-Filling Games
• Upper and lower bounds for finding connected motifs in vertex-colored graphs
• Convex recoloring of paths
• A \(2^{O(k)}\)poly\((n)\) algorithm for the parameterized convex recoloring problem
• Hardness and inapproximability of convex recoloring problems
• Convex recoloring of paths
• An extended formulation of the convex recoloring problem on a tree
• On the complexity of some colorful problems parameterized by treewidth
• A heuristic for the convex recoloring problem in graphs
• Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems
• Strong intractability results for generalized convex recoloring problems
• Strong intractability of generalized convex recoloring problems
• Parameterized complexity of finding small degree-constrained subgraphs
• Tractability and hardness of flood-filling games on trees

This page was built for publication: Connected Coloring Completion for General Graphs: Algorithms and Complexity

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