Fixed-parameter algorithms for graph constraint logic

DOI10.1016/j.tcs.2023.113863arXiv2011.10385OpenAlexW3115261401MaRDI QIDQ6041672

Tatsuhiko Hatanaka, Moritz Mühlenthaler, Felix Hommelsheim, Yusuke Kobayashi, Akira Suzuki, Takehiro Ito

Publication date: 12 May 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

fixed-parameter algorithmscombinatorial reconfigurationnon-deterministic constraint logic

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Complexity of independent set reconfigurability problems
• The complexity of dominating set reconfiguration
• \textsc{Snowman} is \(\mathsf{PSPACE}\)-complete
• On the complexity of reconfiguration problems
• Parameterized complexity of the list coloring reconfiguration problem with graph parameters
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Reconfiguring undirected paths
• Introduction to reconfiguration
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Proof equivalence in MLL is PSPACE-complete
• The complexity of change
• PSPACE-Completeness of Bloxorz and of Games with 2-Buttons
• Parameterized Complexity of Graph Constraint Logic
• Parameterized Algorithms
• Diameter of colorings under Kempe changes
• Rush Hour is PSPACE-complete, or ``Why you should generously tip parking lot attendants

This page was built for publication: Fixed-parameter algorithms for graph constraint logic