Incremental list coloring of graphs, parameterized by conservation
DOI10.1016/J.TCS.2012.12.049zbMATH Open1294.68085OpenAlexW2133773025MaRDI QIDQ391091FDOQ391091
Authors: Sepp Hartung, Rolf Niedermeier 
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
Recommendations
- Incremental list coloring of graphs, parameterized by conservation
- Fixed-parameter tractability of \((n-k)\) list coloring
- Fixed-parameter tractability of \((n-k)\) list coloring
- Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters
- Parameterized complexity of the list coloring reconfiguration problem with graph parameters
data reductionlocal searchparameterized complexityprecoloring extensionproblem kernelincremental clustering
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)
Cites Work
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- On problems without polynomial kernels
- Which problems have strongly exponential complexity?
- Parametrized complexity theory.
- On the compatibility between a graph and a simple order
- Incompressibility through Colors and IDs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Infeasibility of instance compression and succinct PCPs for NP
- Treewidth. Computations and approximations
- On the parameterized complexity of multiple-interval graph problems
- Kernel bounds for disjoint cycles and disjoint paths
- Advice classes of parametrized tractability
- Parameterized coloring problems on chordal graphs
- Reflections on multivariate algorithmics and problem parameterization
- Title not available (Why is that?)
- On the Hardness of Reoptimization
- Generalized coloring for tree-like graphs
- Tight lower bounds for certain parameterized NP-hard problems
- On the complexity of some colorful problems parameterized by treewidth
- Kernelization: new upper and lower bound techniques
- Towards fully multivariate algorithmics: some new results and directions in parameter ecology
- Precoloring extension. I: Interval graphs
- Incremental list coloring of graphs, parameterized by conservation
- Local search: is brute-force avoidable?
- Searching the \(k\)-change neighborhood for TSP is W[1]-hard
- Incremental Clustering and Dynamic Information Retrieval
- Scheduling with incompatible jobs
- Precoloring extension on unit interval graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Precoloring Extension III: Classes of Perfect Graphs
- Parameterized complexity of coloring problems: treewidth versus vertex cover
- Exploring the complexity boundary between coloring and list-coloring
- Minimal cost reconfiguration of data placement in a storage area network
Cited In (14)
- Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics
- Turbocharging treewidth heuristics
- Multistage graph problems on a global budget
- Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs
- Parameterized Dynamic Cluster Editing
- On Covering Segments with Unit Intervals
- Time complexity analysis of randomized search heuristics for the dynamic graph coloring problem
- Dynamic parameterized problems
- On the parameterized complexity of dynamic problems
- Parameterized dynamic cluster editing
- On the parameterized complexity of consensus clustering
- Multistage vertex cover
- Multistage \(s-t\) path: confronting similarity with dissimilarity
- Incremental list coloring of graphs, parameterized by conservation
Uses Software
This page was built for publication: Incremental list coloring of graphs, parameterized by conservation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q391091)
