Independent-set reconfiguration thresholds of hereditary graph classes

DOI10.1016/J.DAM.2018.05.029zbMath1398.05155DBLPjournals/dam/BergJM18arXiv1610.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

zbMATH Keywords

independent setreconfigurationtoken addition removaltoken sliding

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (1)

Can local optimality be used for efficient data reduction?

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

This page was built for publication: Independent-set reconfiguration thresholds of hereditary graph classes