Parameterized complexity of the list coloring reconfiguration problem with graph parameters
From MaRDI portal
Publication:1643161
DOI10.1016/j.tcs.2018.05.005zbMath1395.68153OpenAlexW2963170745MaRDI QIDQ1643161
Xiao Zhou, Takehiro Ito, Tatsuhiko Hatanaka
Publication date: 18 June 2018
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/8106/
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
Fixed-parameter algorithms for graph constraint logic ⋮ Parameterized complexity of optimizing list vertex-coloring through reconfiguration ⋮ Unnamed Item ⋮ Dismantlability, Connectedness, and Mixing in Relational Structures ⋮ Algorithms for Coloring Reconfiguration Under Recolorability Constraints ⋮ Using contracted solution graphs for solving reconfiguration problems
Cites Work
- Unnamed Item
- A dichotomy theorem for circular colouring reconfiguration
- Finding shortest paths between graph colourings
- A survey of the algorithmic aspects of modular decomposition
- On the complexity of reconfiguration problems
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- Reconfiguration in bounded bandwidth and tree-depth
- The coloring reconfiguration problem on specific graph classes
- Linear-time modular decomposition of directed graphs
- Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
- Parameterized Algorithms for Modular-Width
- The complexity of change
- The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs
- The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration
- Homomorphism reconfiguration via homotopy
- Finding paths between 3-colorings
- Randomly coloring sparse random graphs with fewer colors than the maximum degree
- Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances
- Implicat Representation of Graphs
- Transitiv orientierbare Graphen
This page was built for publication: Parameterized complexity of the list coloring reconfiguration problem with graph parameters