Incremental list coloring of graphs, parameterized by conservation

DOI10.1016/j.tcs.2012.12.049zbMath1294.68085OpenAlexW2133773025MaRDI QIDQ391091

Rolf Niedermeier, Sepp Hartung

Publication date: 10 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.12.049

zbMATH Keywords

data reductionlocal searchparameterized complexityprecoloring extensionproblem kernelincremental clustering

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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 (14)

On the ordered list subgraph embedding problems ⋮ Multistage graph problems on a global budget ⋮ Multistage vertex cover ⋮ On the parameterized complexity of dynamic problems ⋮ Multistage \(s-t\) path: confronting similarity with dissimilarity ⋮ Turbocharging treewidth heuristics ⋮ Parameterized dynamic cluster editing ⋮ Time complexity analysis of randomized search heuristics for the dynamic graph coloring problem ⋮ Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs ⋮ On the parameterized complexity of consensus clustering ⋮ Dynamic parameterized problems ⋮ Parameterized Dynamic Cluster Editing ⋮ Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics ⋮ On Covering Segments with Unit Intervals

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Local search: is brute-force avoidable?
• Parameterized complexity of coloring problems: treewidth versus vertex cover
• Infeasibility of instance compression and succinct PCPs for NP
• On the complexity of some colorful problems parameterized by treewidth
• Kernel bounds for disjoint cycles and disjoint paths
• Advice classes of parametrized tractability
• Minimal cost reconfiguration of data placement in a storage area network
• Parameterized coloring problems on chordal graphs
• Searching the \(k\)-change neighborhood for TSP is W[1-hard]
• On the parameterized complexity of multiple-interval graph problems
• On problems without polynomial kernels
• Precoloring extension. I: Interval graphs
• Treewidth. Computations and approximations
• Scheduling with incompatible jobs
• Generalized coloring for tree-like graphs
• Which problems have strongly exponential complexity?
• Parametrized complexity theory.
• Precoloring extension on unit interval graphs
• On the compatibility between a graph and a simple order
• Tight lower bounds for certain parameterized NP-hard problems
• Reflections on Multivariate Algorithmics and Problem Parameterization
• Incremental List Coloring of Graphs, Parameterized by Conservation
• Incompressibility through Colors and IDs
• Towards Fully Multivariate Algorithmics: Some New Results and Directions in Parameter Ecology
• Kernelization: New Upper and Lower Bound Techniques
• Incremental Clustering and Dynamic Information Retrieval
• Precoloring Extension III: Classes of Perfect Graphs
• On the Hardness of Reoptimization
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Exploring the complexity boundary between coloring and list-coloring

This page was built for publication: Incremental list coloring of graphs, parameterized by conservation