Independent-set reconfiguration thresholds of hereditary graph classes
From MaRDI portal
Publication:1801058
DOI10.1016/j.dam.2018.05.029zbMath1398.05155arXiv1610.03766OpenAlexW2538002713WikidataQ60123385 ScholiaQ60123385MaRDI QIDQ1801058
Bart M. P. Jansen, Debankur Mukherjee, Mark T. de Berg
Publication date: 26 October 2018
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1610.03766
Structural characterization of families of graphs (05C75) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Hitting time asymptotics for hard-core interactions on grids
- Kernel bounds for path and cycle problems
- Complexity of independent set reconfigurability problems
- Linear-time algorithm for sliding tokens on trees
- On the parameterized complexity of reconfiguration problems
- On the complexity of reconfiguration problems
- Bounds on isoperimetric values of trees
- Loss networks
- A partial k-arboretum of graphs with bounded treewidth
- Obstruction set isolation for the gate matrix layout problem
- Reconfiguration in bounded bandwidth and tree-depth
- Reconfiguration on sparse graphs
- Multi-color pebble motion on graphs
- Metastability of hard-core dynamics on bipartite graphs
- Introduction to reconfiguration
- Pushing squares around
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- The complexity of change
- Independent Set Reconfiguration in Cographs
- Fast Mixing of Parallel Glauber Dynamics and Low-Delay CSMA Scheduling
- Reconfiguring Independent Sets in Claw-Free Graphs
- Sliding Token on Bipartite Permutation Graphs
- Reducibility among Combinatorial Problems
- Parameterized Algorithms
- Some Theorems on Abstract Graphs
- Reconfigurations in Graphs and Grids
