Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems

DOI10.1007/978-3-540-79228-4_43zbMath1139.68394OpenAlexW1617085997MaRDI QIDQ3502673

Rolf Niedermeier, Oriana Ponta, Falk Hüffner

Publication date: 27 May 2008

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-79228-4_43

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

1.5-approximation algorithm for the 2-convex recoloring problem ⋮ Convex Recoloring Revisited: Complexity and Exact Algorithms ⋮ An extended formulation of the convex recoloring problem on a tree ⋮ The complexity of minimum convex coloring ⋮ Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems ⋮ Quadratic kernelization for convex recoloring of trees ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Revisiting dynamic programming for finding optimal subtrees in trees
• A \(2^{O(k)}\)poly\((n)\) algorithm for the parameterized convex recoloring problem
• Parametrized complexity theory.
• Efficient approximation of convex recolorings
• Partial convex recolorings of trees and galled networks
• Fourier meets M\"{o}bius: fast subset convolution
• Connected Coloring Completion for General Graphs: Algorithms and Complexity
• Quadratic Kernelization for Convex Recoloring of Trees
• Algorithms and Data Structures
• On Exact Complexity of Subgraph Homeomorphism
• The steiner problem in graphs
• Approximation and Online Algorithms

This page was built for publication: Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems