On the parameterized complexity of reconfiguration of connected dominating sets
From MaRDI portal
Publication:832526
DOI10.1007/s00453-021-00909-5OpenAlexW2978392541MaRDI QIDQ832526
Daniel Lokshtanov, Fahad Panolan, Sebastian Siebertz, Amer E. Mouawad
Publication date: 25 March 2022
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2020/13327/
Cites Work
- Kernelization using structural parameters on sparse graph classes
- Reconfiguration of dominating sets
- The complexity of dominating set reconfiguration
- On the parameterized complexity of reconfiguration problems
- On the complexity of reconfiguration problems
- Reconfiguration of list edge-colorings in a graph
- Flip distance between two triangulations of a point set is NP-complete
- Reconfiguration on nowhere dense graph classes
- Reconfiguration on sparse graphs
- Linear time solvable optimization problems on graphs of bounded clique-width
- The \(k\)-dominating graph
- Introduction to reconfiguration
- Connectedness of the graph of vertex-colourings
- The complexity of change
- Domination Problems in Nowhere-Dense Classes
- Flip Distance Is in FPT Time O(n+ k * c^k)
- Lossy Kernels for Connected Dominating Set on Sparse Graphs
- Ground State Connectivity of Local Hamiltonians
- Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas
- Simpler and better approximation algorithms for network design
- Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes
- Kernelization and Sparseness: the case of Dominating Set
- Deciding First-Order Properties of Nowhere Dense Graphs
- Neighborhood complexity and kernelization for nowhere dense classes of graphs
- Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness
- On the number of types in sparse graphs
- Parameterized Algorithms
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: On the parameterized complexity of reconfiguration of connected dominating sets
