Reconfiguration over Tree Decompositions

DOI10.1007/978-3-319-13524-3_21zbMath1456.68132arXiv1405.2447OpenAlexW2962888077MaRDI QIDQ2946023

Naomi Nishimura, Marcin Wrochna, Venkatesh Raman, Amer E. Mouawad

Publication date: 15 September 2015

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Logic in computer science (03B70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (14)

Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas ⋮ Reconfiguration on nowhere dense graph classes ⋮ Shortest reconfiguration of sliding tokens on subclasses of interval graphs ⋮ Rerouting shortest paths in planar graphs ⋮ Computing the flip distance between triangulations ⋮ Parameterized complexity of independent set reconfiguration problems ⋮ Reconfiguration of cliques in a graph ⋮ Sliding Tokens on Block Graphs ⋮ Linear-time algorithm for sliding tokens on trees ⋮ On the parameterized complexity of reconfiguration problems ⋮ Shortest Reconfiguration of Sliding Tokens on a Caterpillar ⋮ Using contracted solution graphs for solving reconfiguration problems ⋮ Introduction to reconfiguration ⋮ On reconfigurability of target sets

This page was built for publication: Reconfiguration over Tree Decompositions