Reconfiguring Independent Sets in Claw-Free Graphs

DOI10.1007/978-3-319-08404-6_8zbMath1417.05199arXiv1403.0359OpenAlexW1495095571MaRDI QIDQ3188884

Marcin Wrochna, Paul Bonsma, Marcin Kaminski

Publication date: 2 September 2014

Published in: Algorithm Theory – SWAT 2014 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (34)

Reconfiguration of colorable sets in classes of perfect graphs ⋮ Finding shortest paths between graph colourings ⋮ Reconfiguration of regular induced subgraphs ⋮ Shortest reconfiguration of sliding tokens on subclasses of interval graphs ⋮ Rerouting shortest paths in planar graphs ⋮ Finding Shortest Paths Between Graph Colourings ⋮ Token sliding on graphs of girth five ⋮ Reconfiguration in bounded bandwidth and tree-depth ⋮ Reconfiguration of maximum-weight \(b\)-matchings in a graph ⋮ On the complexity of distance-\(d\) independent set reconfiguration ⋮ Galactic token sliding ⋮ Parameterized complexity of independent set reconfiguration problems ⋮ On reconfiguration graphs of independent sets under token sliding ⋮ Token sliding on graphs of girth five ⋮ Reconfiguration of cliques in a graph ⋮ Unnamed Item ⋮ Sliding Tokens on Block Graphs ⋮ On girth and the parameterized complexity of token sliding and Token Jumping ⋮ Linear-time algorithm for sliding tokens on trees ⋮ The complexity of dominating set reconfiguration ⋮ Counting independent sets in graphs with bounded bipartite pathwidth ⋮ Unnamed Item ⋮ Reconfiguration of satisfying assignments and subset sums: easy to find, hard to connect ⋮ Shortest Reconfiguration of Sliding Tokens on a Caterpillar ⋮ Independent-set reconfiguration thresholds of hereditary graph classes ⋮ Homomorphism Reconfiguration via Homotopy ⋮ Independent set reconfiguration parameterized by modular-width ⋮ Token sliding on split graphs ⋮ Independent Set Reconfiguration in Cographs and their Generalizations ⋮ The Perfect Matching Reconfiguration Problem ⋮ Using contracted solution graphs for solving reconfiguration problems ⋮ Reconfiguration of Colorable Sets in Classes of Perfect Graphs ⋮ Introduction to reconfiguration ⋮ On reconfigurability of target sets

This page was built for publication: Reconfiguring Independent Sets in Claw-Free Graphs