Reconfiguration of dominating sets

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

zbMATH Keywords

diameterconnectivitysolution spacedominating setreconfiguration graphreconfiguration

Mathematics Subject Classification ID

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