Reconfiguration of dominating sets
From MaRDI portal
DOI10.1007/s10878-015-9947-xzbMath1356.90127arXiv1401.5714OpenAlexW1917899534MaRDI QIDQ346508
Naomi Nishimura, Amer E. Mouawad, Akira Suzuki
Publication date: 29 November 2016
Published in: Lecture Notes in Computer Science, Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1401.5714
Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (26)
Connected \(k\)-dominating graphs ⋮ Decremental Optimization of Dominating Sets Under the Reconfiguration Framework ⋮ Classifying coloring graphs ⋮ On the parameterized complexity of reconfiguration of connected dominating sets ⋮ The Complexity of Dominating Set Reconfiguration ⋮ TS-reconfiguration of dominating sets in circle and circular-arc graphs ⋮ Reconfiguring minimum dominating sets: the \(\gamma\)-graph of a tree ⋮ Reconfiguring dominating sets in some well-covered and other classes of graphs ⋮ On the structure of dominating graphs ⋮ Vertex Cover Reconfiguration and Beyond ⋮ Irredundance trees of diameter 3 ⋮ On dominating graph of graphs, median graphs, partial cubes and complement of minimal dominating sets ⋮ Fast recoloring of sparse graphs ⋮ Unnamed Item ⋮ Linear transformations between dominating sets in the TAR-model ⋮ The complexity of dominating set reconfiguration ⋮ On the parameterized complexity of reconfiguration problems ⋮ On k-Total Dominating Graphs ⋮ Dominating sets reconfiguration under token sliding ⋮ Frozen colourings of bounded degree graphs ⋮ Reconfiguring Minimum Dominating Sets in Trees ⋮ Reconfiguring dominating sets in minor-closed graph classes ⋮ Reconfiguration graphs for dominating sets ⋮ Frozen (Δ + 1)-colourings of bounded degree graphs ⋮ Irredundance graphs ⋮ Introduction to reconfiguration
Cites Work
- Complexity of independent set reconfigurability problems
- On the parameterized complexity of reconfiguration problems
- On the complexity of reconfiguration problems
- Reconfiguration of list edge-colorings in a graph
- Shortest paths between shortest paths
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- Mixing 3-colourings in bipartite graphs
- On the spanning trees of weighted graphs
- Reconfiguration on sparse graphs
- The \(k\)-dominating graph
- Connectedness of the graph of vertex-colourings
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- The complexity of change
- The Complexity of Rerouting Shortest Paths
- Fixed-Parameter Tractability of Token Jumping on Planar Graphs
- Polynomial-Time Algorithm for Sliding Tokens on Trees
- Vertex Cover Reconfiguration and Beyond
- Independent Set Reconfiguration in Cographs
- Finding Shortest Paths Between Graph Colourings
- Reconfiguration of Vertex Covers in a Graph
- Finding paths between 3-colorings
- Approximability of the Subset Sum Reconfiguration Problem
- γ-graphs of graphs
- The Complexity of Dominating Set Reconfiguration
- Reconfiguration of List L(2,1)-Labelings in a Graph
- On the Parameterized Complexity for Token Jumping on Graphs
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
This page was built for publication: Reconfiguration of dominating sets
