Connected Coloring Completion for General Graphs: Algorithms and Complexity
DOI10.1007/978-3-540-73545-8_10zbMATH Open1206.05040OpenAlexW1577433976MaRDI QIDQ3608833FDOQ3608833
Sagi Snir, Igor Razgon, Michael R. Fellows, Benny Chor, Frances 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
Recommendations
- Strong intractability results for generalized convex recoloring problems
- Strong intractability of generalized convex recoloring problems
- Parameterized complexity and approximation issues for the colorful components problems
- Parameterized complexity and approximation issues for the colorful components problems
- On the parameterized complexity of colorful components and related problems
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)
Cited In (17)
- The convex recoloring problem: polyhedra, facets and computational experiments
- Convex Recoloring Revisited: Complexity and Exact Algorithms
- A Survey on the Complexity of Flood-Filling Games
- The complexity of minimum convex coloring
- 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
- A heuristic for the convex recoloring problem in graphs
- On the complexity of some colorful problems parameterized by treewidth
- 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)
