Reconfiguration on nowhere dense graph classes
From MaRDI portal
Publication:1658772
zbMath1393.05171arXiv1707.06775MaRDI QIDQ1658772
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
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
