Reconfiguration on nowhere dense graph classes

zbMath1393.05171arXiv1707.06775MaRDI QIDQ1658772

Sebastian Siebertz

Publication date: 15 August 2018

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1707.06775

zbMATH Keywords

independent setdominating setreconfigurationnowhere dense graphssparse graph classes

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Density (toughness, etc.) (05C42)

Related Items

On the parameterized complexity of reconfiguration of connected dominating sets ⋮ On the complexity of distance-\(d\) independent set reconfiguration ⋮ Unnamed Item ⋮ Reconfiguration on sparse graphs ⋮ Unnamed Item ⋮ Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness ⋮ Introduction to reconfiguration

Cites Work

• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• The complexity of rerouting shortest paths
• 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
• Token jumping in minor-closed classes
• Reconfiguration in bounded bandwidth and tree-depth
• Recoloring graphs via tree decompositions
• Reconfiguration on sparse graphs
• The \(k\)-dominating graph
• Introduction to reconfiguration
• On nowhere dense graphs
• Connectedness of the graph of vertex-colourings
• Parametrized complexity theory.
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Graph Theory
• The complexity of change
• Domination Problems in Nowhere-Dense Classes
• Fixed-Parameter Tractability of Token Jumping on Planar Graphs
• Vertex Cover Reconfiguration and Beyond
• The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration
• Reconfiguration over Tree Decompositions
• Finding paths between 3-colorings
• Approximability of the Subset Sum Reconfiguration Problem
• Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas
• The Complexity of Dominating Set Reconfiguration
• 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
• First order properties on nowhere dense structures
• Neighborhood complexity and kernelization for nowhere dense classes of graphs
• On the number of types in sparse graphs
• On the Parameterized Complexity for Token Jumping on Graphs
• Parameterized Algorithms
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies