Sliding Token on Bipartite Permutation Graphs

Eli Fox-Epstein, Duc A. Hoang, Yota Otachi, Ryuhei Uehara

Type: Book-Chapter

Publication Date: 2015-01-01

Citations: 29

DOI: https://doi.org/10.1007/978-3-662-48971-0_21

View Publication

Locations

Lecture notes in computer science - View
HAL (Le Centre pour la Communication Scientifique Directe) - View

Similar Works

Action	Title	Year	Authors
+	Galactic Token Sliding	2022	Valentin Bartier Nicolás Bousquet Amer E. Mouawad
+	On girth and the parameterized complexity of token sliding and token jumping	2020	Valentin Bartier Nicolás Bousquet Clément Dallard Kyle Lomer Amer E. Mouawad
+	Sliding Tokens on Block Graphs	2017	Duc A. Hoang Eli Fox-Epstein Ryuhei Uehara
+ PDF Chat	On Girth and the Parameterized Complexity of Token Sliding and Token Jumping	2021	Valentin Bartier Nicolás Bousquet Clément Dallard Kyle Lomer Amer E. Mouawad
+	On Girth and the Parameterized Complexity of Token Sliding and Token Jumping.	2020	Valentin Bartier Nicolás Bousquet Clément Dallard Kyle Lomer Amer E. Mouawad
+	On girth and the parameterized complexity of token sliding and token jumping.	2020	Valentin Bartier Nicolás Bousquet Clément Dallard Kyle Lomer Amer E. Mouawad
+	Token sliding on graphs of girth five	2022	Valentin Bartier Nicolás Bousquet Jihad Hanna Amer E. Mouawad Sebastian Siebertz
+ PDF Chat	Token sliding independent set reconfiguration on block graphs	2024	Mathew C. Francis Veena Prabhakaran
+ PDF Chat	The Complexity of Independent Set Reconfiguration on Bipartite Graphs	2018	Daniel Lokshtanov Amer E. Mouawad
+	The complexity of independent set reconfiguration on bipartite graphs	2017	Daniel Lokshtanov Amer E. Mouawad
+	The complexity of independent set reconfiguration on bipartite graphs	2017	Daniel Lokshtanov Amer E. Mouawad
+ PDF Chat	The complexity of independent set reconfiguration on bipartite graphs	2018	Daniel Lokshtanov Amer E. Mouawad
+	Hardness of Token Swapping on Trees	2021	Oswin Aichholzer Erik D. Demaine Matias Korman Jayson Lynch Anna Lubiw Zuzana Masárová Mikhail Rudoy Virginia Vassilevska Williams Nicole Wein
+	Polynomial-Time Algorithms for Sliding Tokens on Cactus Graphs and Block Graphs	2017	Duc A. Hoang Ryuhei Uehara
+	Token Sliding on Split Graphs	2018	Rémy Belmonte Eun Jung Kim Michael Lampis Valia Mitsou Yota Otachi Florian Sikora
+ PDF Chat	Token Sliding on Split Graphs	2019	Rémy Belmonte Eun Jung Kim Michael Lampis Valia Mitsou Yota Otachi Florian Sikora
+ PDF Chat	On Reconfiguration Graphs of Independent Sets Under Token Sliding	2023	David Avis Duc A. Hoang
+	Hardness of Token Swapping on Trees.	2021	Oswin Aichholzer Erik D. Demaine Matias Korman Jayson Lynch Anna Lubiw Zuzana Masárová Mikhail Rudoy Virginia Vassilevska Williams Nicole Wein
+	Some results on Vertex Separator Reconfiguration	2020	Guilherme C. M. Gomes Sérgio H. Nogueira Vinícius Fernandes dos Santos
+	On Reconfiguration Graphs of Independent Sets under Token Sliding	2022	David Avis Duc A. Hoang

Works That Cite This (22)

Action	Title	Year	Authors
+ PDF Chat	Complexity of Token Swapping and Its Variants	2017	Édouard Bonnet Tillmann Miltzow Paweł Rzążewski
+ PDF Chat	Token Sliding on Graphs of Girth Five	2023	Valentin Bartier Nicolás Bousquet Jihad Hanna Amer E. Mouawad Sebastian Siebertz
+ PDF Chat	On Girth and the Parameterized Complexity of Token Sliding and Token Jumping	2021	Valentin Bartier Nicolás Bousquet Clément Dallard Kyle Lomer Amer E. Mouawad
+	Sliding Tokens on Block Graphs	2017	Duc A. Hoang Eli Fox-Epstein Ryuhei Uehara
+ PDF Chat	On the Complexity of Distance-d Independent Set Reconfiguration	2023	Duc A. Hoang
+ PDF Chat	Finding a Reconfiguration Sequence between Longest Increasing Subsequences	2024	Yuuki Aoike Masashi KIYOMI Yasuaki Kobayashi Yota Otachi
+ PDF Chat	Independent Set Reconfiguration Parameterized by Modular-Width	2020	Rémy Belmonte Tesshu Hanaka Michael Lampis Hirotaka Ono Yota Otachi
+ PDF Chat	On Reconfiguration Graphs of Independent Sets Under Token Sliding	2023	David Avis Duc A. Hoang
+	Independent-set reconfiguration thresholds of hereditary graph classes	2018	Mark de Berg Bart M. P. Jansen Debankur Mukherjee
+ PDF Chat	Shortest Reconfiguration Sequence for Sliding Tokens on Spiders	2019	Duc A. Hoang Amanj Khorramian Ryuhei Uehara

Works Cited by This (4)

Action	Title	Year	Authors
+ PDF Chat	Reconfiguring Independent Sets in Claw-Free Graphs	2014	Paul Bonsma Marcin Kamiński Marcin Wrochna
+ PDF Chat	PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation	2005	Robert A. Hearn Erik D. Demaine
+	Reconfiguration in bounded bandwidth and treedepth	2014	Marcin Wrochna
+ PDF Chat	Reconfiguration over Tree Decompositions	2014	Amer E. Mouawad Naomi Nishimura Venkatesh Raman Marcin Wrochna