Independent set reconfiguration parameterized by modular-width
From MaRDI portal
Publication:5918925
DOI10.1007/s00453-020-00700-yzbMath1453.68124arXiv1905.00340OpenAlexW4230754714MaRDI QIDQ5918925
Tesshu Hanaka, Rémy Belmonte, Michael Lampis, Hirotaka Ono, Yota Otachi
Publication date: 3 September 2020
Published in: Algorithmica, Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1905.00340
Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (4)
Invitation to combinatorial reconfiguration ⋮ Further parameterized algorithms for the \(\mathcal{F}\)-free edge deletion problem ⋮ Safe sets and in-dominating sets in digraphs ⋮ Can local optimality be used for efficient data reduction?
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Complexity of independent set reconfigurability problems
- A survey of the algorithmic aspects of modular decomposition
- Linear-time algorithm for sliding tokens on trees
- On the parameterized complexity of reconfiguration problems
- On the complexity of reconfiguration problems
- Token jumping in minor-closed classes
- Reconfiguration in bounded bandwidth and tree-depth
- Token sliding on chordal graphs
- Algorithms parameterized by vertex cover and modular width, through potential maximal cliques
- Algorithmic meta-theorems for restrictions of treewidth
- Introduction to reconfiguration
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- Independent Set Reconfiguration in Cographs and their Generalizations
- Parameterized Algorithms for Modular-Width
- The complexity of change
- Fixed-Parameter Tractability of Token Jumping on Planar Graphs
- Reconfiguring Independent Sets in Claw-Free Graphs
- Sliding Token on Bipartite Permutation Graphs
- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
- Sliding Tokens on a Cactus
- On the Parameterized Complexity for Token Jumping on Graphs
- Parameterized Algorithms
This page was built for publication: Independent set reconfiguration parameterized by modular-width
