Incremental list coloring of graphs, parameterized by conservation
From MaRDI portal
Publication:391091
DOI10.1016/j.tcs.2012.12.049zbMath1294.68085MaRDI 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
data reduction; local search; parameterized complexity; precoloring extension; problem kernel; incremental clustering
68Q25: Analysis of algorithms and problem complexity
05C15: Coloring of graphs and hypergraphs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Parameterized Dynamic Cluster Editing, On Covering Segments with Unit Intervals, Multistage \(s-t\) path: confronting similarity with dissimilarity, Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs, On the ordered list subgraph embedding problems, Dynamic parameterized problems, Multistage graph problems on a global budget, On the parameterized complexity of dynamic problems, Turbocharging treewidth heuristics, On the parameterized complexity of consensus clustering, Multistage vertex cover, Parameterized dynamic cluster editing, Time complexity analysis of randomized search heuristics for the dynamic graph coloring problem, Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics
Uses Software
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
