Zotero Collection: Reconfiguration - 2026-09-06

Cyclically Colored Triangulations: Enumeration and Connectedness of Reconfiguration Graphs

Type: manuscript

Authors: Debrohim, Daniel; Sasaki, Diana; Nunes, Patrícia

Date: 2026/08/26

arXiv URL: https://arxiv.org/abs/2608.26006v1

Attachments:

• storage/7RPYMYB3/Debrohim_Sasaki_Nunes_2026_Cyclically Colored Triangulations [Manuscript].pdf

The Complexity of Boolean Connectivity Problem of $k$-Horn Formulas

Type: manuscript

Authors: Horiyama, Takashi; Mineyoshi, Shoon; Okura, Yuto; Seto, Kazuhisa; Teruyama, Junichi

Date: 2026-08-20

arXiv URL: http://arxiv.org/abs/2608.19569

arXiv ID: 2608.19569 [cs.CC]

DOI: 10.48550/arXiv.2608.19569

Attachments:

• storage/PWDT4RL7/Horiyama et al_2026_The Complexity of Boolean Connectivity Problem of $k$-Horn Formulas [Manuscript].pdf - View on Google Drive

Reconfiguration of Nowhere-zero Flows

Type: manuscript

Authors: Cranston, Daniel W.; Li, Jiaao; Su, Bo; Wang, Zhouningxin; Xu, Ningyan

Date: 2026-06-23

arXiv URL: http://arxiv.org/abs/2606.24685

arXiv ID: 2606.24685 [math.CO]

DOI: 10.48550/arXiv.2606.24685

Attachments:

• storage/BGQUIP8Y/Cranston et al_2026_Reconfiguration of Nowhere-zero Flows [Manuscript].pdf - View on Google Drive

A linear upper bound on the number of moves required for independent set reconfiguration with two sliding tokens

Type: manuscript

Authors: M, Nived J.; Francis, Mathew C.

Date: 2026-08-13

arXiv URL: http://arxiv.org/abs/2608.13130

arXiv ID: 2608.13130 [math.CO]

DOI: 10.48550/arXiv.2608.13130

Attachments:

• storage/CSD7BET4/M_Francis_2026_A linear upper bound on the number of moves required for independent set reconfi [Manuscript].pdf - View on Google Drive

PSPACE-Completeness of Multi-Agent Path Finding for Large Agents

Type: manuscript

Authors: Zhang, Maichi; Kamiyama, Naoyuki; Yoshiwatari, Kanae

Date: 2026-08-13

arXiv URL: http://arxiv.org/abs/2608.12955

arXiv ID: 2608.12955 [cs.CC]

DOI: 10.48550/arXiv.2608.12955

Attachments:

• storage/3363QKI6/Zhang_Kamiyama_Yoshiwatari_2026_PSPACE-Completeness of Multi-Agent Path Finding for Large Agents [Manuscript].pdf - View on Google Drive

Asymptotically Optimal Inapproximability of Maxmin $k$-Cut Reconfiguration

Type: manuscript

Authors: Hirahara, Shuichi; Ohsaka, Naoto

Date: 2025-03-29

arXiv URL: http://arxiv.org/abs/2410.03416

arXiv ID: 2410.03416 [cs.CC]

DOI: 10.48550/arXiv.2410.03416

Attachments:

• storage/TMZLYUC8/Hirahara_Ohsaka_2025_Asymptotically Optimal Inapproximability of Maxmin $k$-Cut Reconfiguration [Manuscript].pdf - View on Google Drive

Computing distances is FPT on graph associahedra and W[2]-hard on hypergraphic polytopes

Type: manuscript

Authors: Cunha, Luís Felipe I.; Sau, Ignasi; Souza, Uéverton S.; Valencia-Pabon, Mario

Date: 2026-03-23

arXiv URL: http://arxiv.org/abs/2504.18338

arXiv ID: 2504.18338 [cs.DS]

DOI: 10.48550/arXiv.2504.18338

Attachments:

• storage/QHGPT4WB/Cunha et al_2026_Computing distances is FPT on graph associahedra and W[2]-hard on hypergraphic p [Manuscript].pdf - View on Google Drive

Constrained Flips in Plane Spanning Trees

Type: manuscript

Authors: Aichholzer, Oswin; Dorfer, Joseph; Vogtenhuber, Birgit

Date: 2025-08-21

arXiv URL: http://arxiv.org/abs/2508.15520

arXiv ID: 2508.15520 [cs.CG]

DOI: 10.48550/arXiv.2508.15520

Attachments:

• storage/YPMR3EIW/Aichholzer_Dorfer_Vogtenhuber_2025_Constrained Flips in Plane Spanning Trees [Manuscript].pdf - View on Google Drive

The realization graph of every degree sequence has a Hamilton path

Type: manuscript

Authors: Hladík, Petr; Fink, Jiří

Date: 2026-07-20

arXiv URL: http://arxiv.org/abs/2607.18146

arXiv ID: 2607.18146 [math.CO]

DOI: 10.48550/arXiv.2607.18146

Attachments:

• storage/MN7WKXUU/Hladík_Fink_2026_The realization graph of every degree sequence has a Hamilton path [Manuscript].pdf - View on Google Drive

NP-Hardness of Connected Components Reconfiguration under Component Jumping on Caterpillar Graphs

Type: manuscript

Authors: Kitamura, Naoki; Kawaguchi, Seitaro; Terashima, Yuya; Izumi, Taisuke

Date: 2026-07-17

arXiv URL: http://arxiv.org/abs/2607.15737

arXiv ID: 2607.15737 [cs.DS]

DOI: 10.48550/arXiv.2607.15737

Attachments:

• storage/KQK47EYQ/Kitamura et al_2026_NP-Hardness of Connected Components Reconfiguration under Component Jumping on C [Manuscript].pdf - View on Google Drive

Hamiltonicity of Bell and Stirling Colour Graphs

Type: manuscript

Authors: Finbow, Stephen; MacGillivray, Gary

Date: 2025-12-15

arXiv URL: http://arxiv.org/abs/2512.13864

arXiv ID: 2512.13864 [math.CO]

DOI: 10.48550/arXiv.2512.13864

Attachments:

• storage/HXNYIM38/Finbow_MacGillivray_2025_Hamiltonicity of Bell and Stirling Colour Graphs [Manuscript].pdf - View on Google Drive

Reconfiguring Subgraphs with Extra Resources

Type: manuscript

Authors: Fong, Jason; Kam, Jeffrey; Wong, Steven

Date: 2026-07-11

arXiv URL: http://arxiv.org/abs/2607.10399

arXiv ID: 2607.10399 [cs.DM]

DOI: 10.48550/arXiv.2607.10399

Attachments:

• storage/ZPKNM9SP/Fong_Kam_Wong_2026_Reconfiguring Subgraphs with Extra Resources [Manuscript].pdf - View on Google Drive

Independent Set Reconfiguration on Threshold Signed Graphs

Type: manuscript

Authors: Alaoui, Ziad Ismaili

Date: 2026-07-12

arXiv URL: http://arxiv.org/abs/2607.10629

arXiv ID: 2607.10629 [cs.DS]

DOI: 10.48550/arXiv.2607.10629

Attachments:

• storage/GRSMM92M/Alaoui_2026_Independent Set Reconfiguration on Threshold Signed Graphs [Manuscript].pdf - View on Google Drive

Hamilton paths and cycles in flip graphs of (almost-)perfect matchings

Type: manuscript

Authors: Brenner, Sofia; Dallant, Justin; Kleist, Linda; Lauff, Robert; Mütze, Torsten; Schürenberg, Torben

Date: 2026/07/06

arXiv URL: https://arxiv.org/abs/2607.04687v2

Attachments:

• storage/BLIDPA9X/Brenner et al_2026_Hamilton paths and cycles in flip graphs of (almost-)perfect matchings [Manuscript].pdf - View on Google Drive

On the recolorability of $(2K_2, K_4)$-free graphs

Type: manuscript

Authors: Echeverría, Henry; Henderschedt, Owen

Date: 2026-07-08

arXiv URL: http://arxiv.org/abs/2607.07860

arXiv ID: 2607.07860 [math.CO]

DOI: 10.48550/arXiv.2607.07860

Attachments:

• storage/WCZSGIK3/Echeverría_Henderschedt_2026_On the recolorability of $(2K_2, K_4)$-free graphs [Manuscript].pdf - View on Google Drive

FO Value Discovery and Partial Vertex Cover Discovery

Type: manuscript

Authors: Gerhard, Enna; Maaz, Stephanie; Schott, Pascale; Siebertz, Sebastian; Wodkte, Jan

Date: 2026-07-07

arXiv URL: http://arxiv.org/abs/2607.06446

arXiv ID: 2607.06446 [cs.DM]

DOI: 10.48550/arXiv.2607.06446

Attachments:

• storage/DI9HNKSH/Gerhard et al_2026_FO Value Discovery and Partial Vertex Cover Discovery [Manuscript].pdf - View on Google Drive

Token sliding independent set reconfiguration on graphs with few $P_4$'s

Type: manuscript

Authors: Busolini, Lucia; Valencia-Pabon, Mario

Date: 2026-06-30

arXiv URL: http://arxiv.org/abs/2606.31815

arXiv ID: 2606.31815 [cs.DS]

DOI: 10.48550/arXiv.2606.31815

Attachments:

• storage/7GGDDLKU/Busolini_Valencia-Pabon_2026_Token sliding independent set reconfiguration on graphs with few $P_4$'s [Manuscript].pdf - View on Google Drive

Token-sliding realizability for complements, Cartesian-products, and grid graph families

Type: manuscript

Authors: Hoang, Duc A.

Date: 2026-06-02

arXiv URL: http://arxiv.org/abs/2606.03765

arXiv ID: 2606.03765 [math.CO]

DOI: 10.48550/arXiv.2606.03765

Attachments:

• storage/JJNE3X6X/Hoang_2026_Token-sliding realizability for complements, Cartesian-products, and grid graph [Manuscript].pdf - View on Google Drive

On Realizing Reconfiguration Graphs of Cliques

Type: manuscript

Authors: Hoang, Duc A.

Date: 2026

arXiv URL: https://arxiv.org/abs/2604.03567

DOI: 10.48550/ARXIV.2604.03567

Attachments:

• storage/TL67YRHC/Hoang_2026_On Realizing Reconfiguration Graphs of Cliques [Manuscript].pdf - View on Google Drive

Reconfiguration graphs of $K_{2,3}$-minor-free graphs

Type: manuscript

Authors: Gu, Ruijuan; Lei, Hui; Li, Zhaoxiang; Ma, Yulai; Wang, Susu

Date: 2026

arXiv URL: https://arxiv.org/abs/2605.31225

DOI: 10.48550/ARXIV.2605.31225

Attachments:

• storage/ZL6R7W49/Gu et al_2026_Reconfiguration graphs of $K_{2,3}$-minor-free graphs [Manuscript].pdf - View on Google Drive

Conjectured Bounds for 2-Local Hamiltonians via Token Graphs

Type: manuscript

Authors: Apte, Anuj; Parekh, Ojas; Sud, James

Date: 2025

arXiv URL: https://arxiv.org/abs/2506.03441

DOI: 10.48550/ARXIV.2506.03441

Attachments:

• storage/5XXZZAZS/Apte_Parekh_Sud_2025_Conjectured Bounds for 2-Local Hamiltonians via Token Graphs [Manuscript].pdf - View on Google Drive

Tight constructions for reconfigurations of independent transversals

Type: manuscript

Authors: Wdowinski, Ronen

Date: 2026-04-23

arXiv URL: http://arxiv.org/abs/2604.21576

arXiv ID: 2604.21576 [math]

DOI: 10.48550/arXiv.2604.21576

Attachments:

• storage/J7JQMV3M/Wdowinski_2026_Tight constructions for reconfigurations of independent transversals [Manuscript].pdf - View on Google Drive

On (In)approximability of MaxMin Independent Set Reconfiguration

Type: manuscript

Authors: Hoang, Hung P.; Ohsaka, Naoto; Saito, Rin; Tamura, Yuma

Date: 2026-04-29

arXiv URL: http://arxiv.org/abs/2604.26714

arXiv ID: 2604.26714 [cs]

DOI: 10.48550/arXiv.2604.26714

Attachments:

• storage/QYTX66UL/Hoang et al_2026_On (In)approximability of MaxMin Independent Set Reconfiguration [Manuscript].pdf - View on Google Drive

Separating Feasibility and Movement in Solution Discovery: The Case of Path Discovery

Type: manuscript

Authors: Bergen, Hanno von; Fastenau, Larissa; Gerhard, Enna; Lorenz, Nicola; Maaz, Stephanie; Mouawad, Amer E.; Rabinovich, Roman; Schirrmacher, Nicole; Schmand, Daniel; Siebertz, Sebastian; Trinh, Mai

Date: 2026-04-30

arXiv URL: http://arxiv.org/abs/2604.27802

arXiv ID: 2604.27802 [cs]

DOI: 10.48550/arXiv.2604.27802

Attachments:

• storage/R9D8LW8A/Bergen et al_2026_Separating Feasibility and Movement in Solution Discovery [Manuscript].pdf - View on Google Drive

Finding Shortest Reconfiguration Sequences on Independent Set Polytopes

Type: manuscript

Authors: Cardinal, Jean; Mann, Kevin; Suzuki, Akira; Suzuki, Takahiro; Tamura, Yuma; Zhou, Xiao

Date: 2026-04-27

arXiv URL: http://arxiv.org/abs/2604.24132

arXiv ID: 2604.24132 [cs]

DOI: 10.48550/arXiv.2604.24132

Attachments:

• storage/FKXL3JLZ/Cardinal et al_2026_Finding Shortest Reconfiguration Sequences on Independent Set Polytopes [Manuscript].pdf - View on Google Drive

Nowhere-zero flow reconfiguration

Type: manuscript

Authors: Esperet, Louis; Hendrey, Kevin; Lagoutte, Aurélie; Marseloo, Margaux; Norin, Sergey; Steiner, Raphael

Date: 2025

arXiv URL: https://arxiv.org/abs/2512.17342

DOI: 10.48550/ARXIV.2512.17342

Attachments:

• storage/EZHMMBUZ/Esperet et al_2025_Nowhere-zero flow reconfiguration [Manuscript].pdf - View on Google Drive

Reconstructing a graph from its Bell colouring graph

Type: manuscript

Authors: Hearn, Brian

Date: 2026-04-14

arXiv URL: http://arxiv.org/abs/2604.13005

arXiv ID: 2604.13005 [math]

DOI: 10.48550/arXiv.2604.13005

Attachments:

• storage/IQ4ZRQ9F/Hearn_2026_Reconstructing a graph from its Bell colouring graph [Manuscript].pdf - View on Google Drive

Complexity Thresholds for the Constrained Colored Token Swapping Problem

Type: manuscript

Authors: Bilò, Davide; Leucci, Stefano; Martinelli, Andrea

Date: 2026-01-14

arXiv URL: http://arxiv.org/abs/2601.09681

arXiv ID: 2601.09681 [cs]

DOI: 10.48550/arXiv.2601.09681

Attachments:

• storage/7K7JMYBH/Bilò_Leucci_Martinelli_2026_Complexity Thresholds for the Constrained Colored Token Swapping Problem [Manuscript].pdf - View on Google Drive

On Generalized Token Graphs

Type: manuscript

Authors: Song, Xiaodi; Dalfó, Cristina; Fiol, Miquel Àngel; Mora, Mercè; Zhang, Shenggui

Date: 2026-04-06

arXiv URL: http://arxiv.org/abs/2604.04845

arXiv ID: 2604.04845 [math]

DOI: 10.48550/arXiv.2604.04845

Attachments:

• storage/XVA5WERZ/Song et al_2026_On Generalized Token Graphs [Manuscript].pdf - View on Google Drive

A Gray code for arborescences of tournaments

Type: manuscript

Authors: Bonamy, Marthe; Hoffmann, Michael; Legrand-Duchesne, Clément; Rote, Günter

Date: 2026/03/30

arXiv URL: https://arxiv.org/abs/2603.28614v1

Attachments:

• storage/FIKECNV5/Bonamy et al_2026_A Gray code for arborescences of tournaments [Manuscript].pdf - View on Google Drive

Flip Distance of Triangulations of Convex Polygons / Rotation Distance of Binary Trees is NP-complete

Type: manuscript

Authors: Dorfer, Joseph

Date: 2026-02-26

arXiv URL: http://arxiv.org/abs/2602.22874

arXiv ID: 2602.22874 [cs]

DOI: 10.48550/arXiv.2602.22874

Attachments:

• storage/7EAZV8I3/Dorfer_2026_Flip Distance of Triangulations of Convex Polygons Rotation Distance of Binary [Manuscript].pdf - View on Google Drive

Kempe Equivalent List Colorings Revisited

Type: manuscript

Authors: Chakraborty, Dibyayan; Feghali, Carl; Mahmoud, Reem

Date: 2024-02-10

arXiv URL: http://arxiv.org/abs/2211.16728

arXiv ID: 2211.16728 [math]

DOI: 10.48550/arXiv.2211.16728

Attachments:

• storage/SWYPNJEU/Chakraborty_Feghali_Mahmoud_2024_Kempe Equivalent List Colorings Revisited [Manuscript].pdf - View on Google Drive

Exact Dominion of the Prism Graph: Enumeration by Congruence Class via Cyclic Words

Type: manuscript

Authors: Allagan, Julian

Date: 2026-01-07

arXiv URL: http://arxiv.org/abs/2601.03488

arXiv ID: 2601.03488 [math]

DOI: 10.48550/arXiv.2601.03488

Attachments:

• storage/IKFJWJAR/Allagan_2026_Exact Dominion of the Prism Graph [Manuscript].pdf - View on Google Drive

ETH Flippers Approach to Parallel Reconfiguration of Triangulations: SAT formulation and Heuristics

Type: manuscript

Authors: Battini, Lorenzo; Milenković, Marko

Date: 2026-03-23

arXiv URL: http://arxiv.org/abs/2603.22456

arXiv ID: 2603.22456 [cs]

DOI: 10.48550/arXiv.2603.22456

Attachments:

• storage/L6Z9EVW4/Battini_Milenković_2026_ETH Flippers Approach to Parallel Reconfiguration of Triangulations [Manuscript].pdf - View on Google Drive

Flip Distance of Non-Crossing Spanning Trees: NP-Hardness and Improved Bounds

Type: manuscript

Authors: Bjerkevik, Håvard Bakke; Dorfer, Joseph; Kleist, Linda; Ueckerdt, Torsten; Vogtenhuber, Birgit

Date: 2026-03-23

arXiv URL: http://arxiv.org/abs/2603.22262

arXiv ID: 2603.22262 [cs]

DOI: 10.48550/arXiv.2603.22262

Attachments:

• storage/MZUD3ANI/Bjerkevik et al_2026_Flip Distance of Non-Crossing Spanning Trees [Manuscript].pdf - View on Google Drive

Shadoks Approach to Parallel Reconfiguration of Triangulations

Type: manuscript

Authors: Fonseca, Guilherme D. da; Feschet, Fabien; Gerard, Yan

Date: 2026-03-22

arXiv URL: http://arxiv.org/abs/2603.21293

arXiv ID: 2603.21293 [cs]

DOI: 10.48550/arXiv.2603.21293

Attachments:

• storage/E63IPQPP/Fonseca_Feschet_Gerard_2026_Shadoks Approach to Parallel Reconfiguration of Triangulations [Manuscript].pdf - View on Google Drive

Reconfiguration graph for vertex colorings for ($P_2$+$P_3$, $C_4$)-free graphs

Type: manuscript

Authors: Belavadi, M.; Karthick, T.

Date: 2026-02-24

arXiv URL: http://arxiv.org/abs/2509.03190

arXiv ID: 2509.03190 [math]

DOI: 10.48550/arXiv.2509.03190

Attachments:

• storage/TZRE2BNP/Belavadi_Karthick_2026_Reconfiguration graph for vertex colorings for ($P_2$+$P_3$, $C_4$)-free graphs [Preprint].pdf - View on Google Drive

Biclique Reconfiguration in Bipartite Graphs

Type: manuscript

Authors: Otachi, Yota; Toyoda, Emi

Date: 2026/03/18

arXiv URL: https://arxiv.org/abs/2603.17706v1

Attachments:

• storage/47HKPTI9/Otachi_Toyoda_2026_Biclique Reconfiguration in Bipartite Graphs [Manuscript].pdf - View on Google Drive

Structural Properties of Shortest Flip Sequences Between Plane Spanning Trees

Type: manuscript

Authors: Aichholzer, Oswin; Dorfer, Joseph; Kramer, Peter; Rieck, Christian; Vogtenhuber, Birgit

Date: 2026-03-05

arXiv URL: http://arxiv.org/abs/2603.05205

arXiv ID: 2603.05205 [cs]

DOI: 10.48550/arXiv.2603.05205

Attachments:

• storage/SCFYV75A/Aichholzer_Dorfer_Kramer_2026_Structural Properties of Shortest Flip Sequences Between Plane Spanning Trees [Manuscript].pdf - View on Google Drive

Symbolic Functional Decomposition: A Reconfiguration Approach

Type: manuscript

Authors: Oliveira, Mateus de Oliveira; Broeck, Wim Van den

Date: 2026-01-13

arXiv URL: http://arxiv.org/abs/2601.08354

arXiv ID: 2601.08354 [cs]

Attachments:

• storage/9G84ZCNU/Oliveira_Broeck_2026_Symbolic Functional Decomposition [Manuscript].pdf - View on Google Drive

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results

Type: manuscript

Authors: S, Karthik C.; Manurangsi, Pasin

Date: 2024/1/14

Attachments:

• storage/TC9WRRRL/S_Manurangsi_2024_On Inapproximability of Reconfiguration Problems [Manuscript].pdf - View on Google Drive

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results

Type: manuscript

Authors: Guruswami, Venkatesan; S, Karthik C.; Manurangsi, Pasin; Ren, Xuandi; Wu, Kewen

Date: 2025-09-23

arXiv URL: http://arxiv.org/abs/2312.17140

arXiv ID: 2312.17140 [cs]

Attachments:

• storage/Z8PEV4RQ/Guruswami et al_2025_On Inapproximability of Reconfiguration Problems [Manuscript].pdf - View on Google Drive

Tile Reconfiguration by a Finite Automaton

Type: manuscript

Authors: Friemel, Jonas; Liedtke, David; Scheffer, Christian

Date: 2025-11-17

arXiv URL: http://arxiv.org/abs/2501.08663

arXiv ID: 2501.08663 [cs]

Attachments:

• storage/XMLME4MY/Friemel_Liedtke_Scheffer_2025_Tile Reconfiguration by a Finite Automaton [Preprint].pdf - View on Google Drive

A Universal In-Place Reconfiguration Algorithm for Sliding Cube-Shaped Robots in a Quadratic Number of Moves

Type: manuscript

Authors: Abel, Zachary; Akitaya, Hugo A.; Kominers, Scott Duke; Korman, Matias; Stock, Frederick

Date: 2024-03-14

arXiv URL: http://arxiv.org/abs/0802.3414

arXiv ID: 0802.3414

Attachments:

• storage/PIXABLQP/Abel et al_2024_A Universal In-Place Reconfiguration Algorithm for Sliding Cube-Shaped Robots in a Quadratic Number of Moves [Manuscript].pdf - View on Google Drive

Towards an algebraic approach to the reconfiguration CSP

Type: manuscript

Authors: Kimura, Kei

Date: 2025-11-28

arXiv URL: http://arxiv.org/abs/2511.22914

arXiv ID: 2511.22914 [cs]

Attachments:

• storage/D4JVG5YZ/Kimura_2025_Towards an algebraic approach to the reconfiguration CSP [Manuscript].pdf - View on Google Drive

Subexponential and Parameterized Mixing Times of Glauber Dynamics on Independent Sets

Type: manuscript

Authors: Marin, Malory

Date: 2025-11-21

arXiv URL: http://arxiv.org/abs/2504.18427

arXiv ID: 2504.18427 [cs]

Attachments:

• storage/28CLXUXF/Marin_2025_Subexponential and Parameterized Mixing Times of Glauber Dynamics on Independent Sets [Preprint].pdf - View on Google Drive

Kempe equivalence and quadratic toric rings

Type: manuscript

Authors: Ohsugi, Hidefumi; Tsuchiya, Akiyoshi

Date: 2025-10-22

arXiv URL: http://arxiv.org/abs/2303.12824

arXiv ID: 2303.12824 [math]

Attachments:

• storage/YZXUDATP/Ohsugi_Tsuchiya_2025_Kempe equivalence and quadratic toric rings [Manuscript].pdf - View on Google Drive

Reflexive Digraph Reconfiguration by Orientation Strings

Type: manuscript

Authors: Pullas, David Emmanuel Pazmiño; Siggers, Mark

Date: 2025-03-18

arXiv URL: http://arxiv.org/abs/2501.01599

arXiv ID: 2501.01599 [math]

Attachments:

• storage/RBHCGDXR/Pullas_Siggers_2025_Reflexive Digraph Reconfiguration by Orientation Strings [Manuscript].pdf - View on Google Drive

Reflexive Digraph Reconfiguration by Words

Type: manuscript

Authors: Pullas, David Emmanuel Pazmiño; Siggers, Mark

Date: 2025-01-03

arXiv URL: http://arxiv.org/abs/2501.01599

arXiv ID: 2501.01599 [math]

Attachments:

• storage/6A7USYKP/Pullas_Siggers_2025_Reflexive Digraph Reconfiguration by Words [Manuscript].pdf - View on Google Drive

Parameterised algorithms for temporally satisfying reconfiguration problems

Type: manuscript

Authors: Davot, Tom; Enright, Jessica; Larios-Jones, Laura

Date: 2025-09-19

arXiv URL: http://arxiv.org/abs/2502.11961

arXiv ID: 2502.11961 [cs]

Attachments:

• storage/NSHNFR29/Davot_Enright_Larios-Jones_2025_Parameterised algorithms for temporally satisfying reconfiguration problems [Manuscript].pdf - View on Google Drive

Flips and Merge-Width in Sparse Graphs

Type: manuscript

Authors: Drabik, Karolina; Dumas, Maël; Mählmann, Nikolas; Przybyszewski, Wojciech; Toruńczyk, Szymon

Date: 2026/02/13

arXiv URL: https://arxiv.org/abs/2602.12926v1

Attachments:

• storage/SCLUHB45/Drabik et al_2026_Flips and Merge-Width in Sparse Graphs [Manuscript].pdf - View on Google Drive

Exploring the 3-Token Graph of Particular Graphs

Type: manuscript

Authors: Susanti, Yeni; Yuliana, Arizka; Bagaskara, Widi; Susanti, Yeni

Date: 2025-05-21

DOI: 10.20944/preprints202505.1605.v1

Attachments:

• storage/E7UAPVRD/Susanti et al_2025_Exploring the 3-Token Graph of Particular Graphs [Manuscript].pdf - View on Google Drive

Higher Hardness Results for the Reconfiguration of Odd Matchings

Type: manuscript

Authors: Dorfer, Joseph

Date: 2026-02-10

arXiv URL: http://arxiv.org/abs/2602.09573

arXiv ID: 2602.09573 [cs]

Attachments:

• storage/B2P9ICZD/Dorfer_2026_Higher Hardness Results for the Reconfiguration of Odd Matchings [Manuscript].pdf - View on Google Drive

Solution discovery via reconfiguration for problems in P

Type: manuscript

Authors: Grobler, Mario; Maaz, Stephanie; Megow, Nicole; Mouawad, Amer E.; Ramamoorthi, Vijayaragunathan; Schmand, Daniel; Siebertz, Sebastian

Date: 2023-11-22

arXiv URL: http://arxiv.org/abs/2311.13478

arXiv ID: 2311.13478 [cs, math]

Attachments:

• storage/6AWL7M6A/Grobler et al_2023_Solution discovery via reconfiguration for problems in P [Manuscript].pdf - View on Google Drive

A Note on Reconfiguration Graphs of Cliques

Type: manuscript

Authors: Lam, Quan N.; Phan, Huu An; Hoang, Duc A.

Date: 2025-12-12

arXiv URL: http://arxiv.org/abs/2506.07821

arXiv ID: 2506.07821 [math]

Attachments:

• storage/3BIQ7AZM/Lam_Phan_Hoang_2025_A Note on Reconfiguration Graphs of Cliques [Manuscript].pdf - View on Google Drive

Token sliding independent set reconfiguration on block graphs

Type: manuscript

Authors: Francis, Mathew C.; Prabhakaran, Veena

Date: 2024-10-09

arXiv URL: http://arxiv.org/abs/2410.07060

arXiv ID: 2410.07060

Attachments:

• storage/3SN8AB7W/Francis_Prabhakaran_2024_Token sliding independent set reconfiguration on block graphs [Manuscript].pdf - View on Google Drive

Gap Preserving Reductions between Reconfiguration Problems

Type: manuscript

Authors: Ohsaka, Naoto

Date: 2022-12-08

arXiv URL: http://arxiv.org/abs/2212.04207

arXiv ID: 2212.04207 [cs]

Attachments:

• storage/5XF7DQXV/Ohsaka_2022_Gap Preserving Reductions between Reconfiguration Problems [Manuscript].pdf - View on Google Drive

On the Connectivity of the Flip Graph of Plane Spanning Paths

Type: manuscript

Authors: Kleist, Linda; Kramer, Peter; Rieck, Christian

Date: 2024-07-04

arXiv URL: http://arxiv.org/abs/2407.03912

arXiv ID: 2407.03912 [cs]

Attachments:

• storage/IB4CZM4C/Kleist_Kramer_Rieck_2024_On the Connectivity of the Flip Graph of Plane Spanning Paths [Manuscript].pdf - View on Google Drive

Extremal diameters of 3-coloring graphs of trees

Type: manuscript

Authors: Asgarli, Shamil; Krehbiel, Sara; MacLean, Simon; Zaimi, Gjergji

Date: 2025/12/03

arXiv URL: https://arxiv.org/abs/2512.03789v1

Attachments:

• storage/K7MT3I64/Asgarli et al_2025_Extremal diameters of 3-coloring graphs of trees [Manuscript].pdf - View on Google Drive

Input-Sensitive Reconfiguration of Sliding Cubes

Type: manuscript

Authors: Akitaya, Hugo; Korman, Matias; Stock, Frederick

Date: 2025-07-05

arXiv URL: http://arxiv.org/abs/2507.04170

arXiv ID: 2507.04170 [cs]

Attachments:

• storage/9GJTWMQ8/Akitaya_Korman_Stock_2025_Input-Sensitive Reconfiguration of Sliding Cubes [Manuscript].pdf - View on Google Drive

Efficient Reconfiguration of Tile Arrangements by a Single Active Robot

Type: manuscript

Authors: Becker, Aaron T.; Fekete, Sándor P.; Friemel, Jonas; Kosfeld, Ramin; Kramer, Peter; Kube, Harm; Rieck, Christian; Scheffer, Christian; Schmidt, Arne

Date: 2025-06-27

arXiv URL: http://arxiv.org/abs/2502.09299

arXiv ID: 2502.09299 [cs]

Attachments:

• storage/76SIZDWS/Becker et al_2025_Efficient Reconfiguration of Tile Arrangements by a Single Active Robot [Manuscript].pdf - View on Google Drive

Hall's theorem for reconfigurations and higher dimensional topological connectedness

Type: manuscript

Authors: Wdowinski, Ronen

Date: 2025-11-06

arXiv URL: http://arxiv.org/abs/2511.04863

arXiv ID: 2511.04863 [math]

Attachments:

• storage/MZIT3M6B/Wdowinski_2025_Hall's theorem for reconfigurations and higher dimensional topological connectedness [Preprint].pdf - View on Google Drive

Independent set reconfiguration in H-free graphs

Type: manuscript

Authors: Bartier, Valentin; Bousquet, Nicolas; Mühlenthaler, Moritz

Date: 2024-02-05

arXiv URL: http://arxiv.org/abs/2402.03063

arXiv ID: 2402.03063 [cs]

Attachments:

• storage/47GJDLYH/Bartier_Bousquet_Mühlenthaler_2024_Independent set reconfiguration in H-free graphs [Manuscript].pdf - View on Google Drive

Kempe equivalence of 4-colourings of some plane triangulations

Type: manuscript

Authors: Florek, Jan

Date: 2025-11-01

arXiv URL: http://arxiv.org/abs/2511.00485

arXiv ID: 2511.00485 [math]

Attachments:

• storage/DSMLEISB/Florek_2025_Kempe equivalence of 4-colourings of some plane triangulations [Preprint].pdf - View on Google Drive

Settling Weighted Token Swapping up to Algorithmic Barriers

Type: manuscript

Authors: Wein, Nicole; Zhang, Guanyu Tony

Date: 2025-07-31

arXiv URL: http://arxiv.org/abs/2507.22450

arXiv ID: 2507.22450 [cs]

Attachments:

• storage/RRBRYY4S/Wein_Zhang_2025_Settling Weighted Token Swapping up to Algorithmic Barriers [Manuscript].pdf - View on Google Drive

Kempe changes in $H$-free graphs

Type: manuscript

Authors: Belavadi, Manoj; Cameron, Kathie

Date: 2025-11-30

arXiv URL: http://arxiv.org/abs/2512.00695

arXiv ID: 2512.00695 [math]

Attachments:

• storage/DYXZHX92/Belavadi_Cameron_2025_Kempe changes in $H$-free graphs [Manuscript].pdf - View on Google Drive

Solution Discovery for Vertex Cover, Independent Set, Dominating Set, and Feedback Vertex Set

Type: manuscript

Authors: Saito, Rin; Sommer, Anouk; Suga, Tatsuhiro; Suzuki, Takahiro; Tamura, Yuma

Date: 2025-11-28

arXiv URL: http://arxiv.org/abs/2511.23012

arXiv ID: 2511.23012 [cs]

Attachments:

• storage/T8M7YSR6/Saito et al_2025_Solution Discovery for Vertex Cover, Independent Set, Dominating Set, and Feedback Vertex Set [Manuscript].pdf - View on Google Drive

Reconfiguration of basis pairs in regular matroids

Type: manuscript

Authors: Bérczi, Kristóf; Mátravölgyi, Bence; Schwarcz, Tamás

Date: 2023-11-13

arXiv URL: http://arxiv.org/abs/2311.07130

arXiv ID: 2311.07130 [cs, math]

Attachments:

• storage/BIGXR8CS/Bérczi_Mátravölgyi_Schwarcz_2023_Reconfiguration of basis pairs in regular matroids [Manuscript].pdf - View on Google Drive

Coloring Reconfiguration under Color Swapping

Type: manuscript

Authors: Fuchs, Janosch; Saito, Rin; Suga, Tatsuhiro; Suzuki, Takahiro; Tamura, Yuma

Date: 2025-11-11

arXiv URL: http://arxiv.org/abs/2511.06473

arXiv ID: 2511.06473 [cs]

Attachments:

• storage/94NM7UXE/Fuchs et al_2025_Coloring Reconfiguration under Color Swapping [Manuscript].pdf - View on Google Drive

Kempe changes in degenerate graphs

Type: manuscript

Authors: Bonamy, Marthe; Delecroix, Vincent; Legrand-Duchesne, Clément

Date: 2021-12-04

arXiv URL: http://arxiv.org/abs/2112.02313

arXiv ID: 2112.02313

Attachments:

• storage/6CFZPH7U/Bonamy_Delecroix_Legrand-Duchesne_2021_Kempe changes in degenerate graphs [Manuscript].pdf - View on Google Drive

Parallel Token Swapping for Qubit Routing

Type: manuscript

Authors: Bansal, Ishan; Günlük, Oktay; Shapley, Richard

Date: 2024-11-27

arXiv URL: http://arxiv.org/abs/2411.18581

arXiv ID: 2411.18581 [cs]

Attachments:

• storage/XLB44AGY/Bansal_Günlük_Shapley_2024_Parallel Token Swapping for Qubit Routing [Manuscript].pdf - View on Google Drive

Sequentially Swapping Tokens: Further on Graph Classes

Type: manuscript

Authors: Kiya, Hironori; Okada, Yuto; Ono, Hirotaka; Otachi, Yota

Date: 2022-10-25

arXiv URL: http://arxiv.org/abs/2210.02835

arXiv ID: 2210.02835 [cs]

Attachments:

• storage/Q6EE2ZM2/Kiya et al_2022_Sequentially Swapping Tokens [Manuscript].pdf - View on Google Drive

Reconfiguration and Enumeration of Optimal Cyclic Ladder Lotteries

Type: manuscript

Authors: Nozaki, Yuta; Wasa, Kunihiro; Yamanaka, Katsuhisa

Date: 2024-05-25

arXiv URL: http://arxiv.org/abs/2405.16408

arXiv ID: 2405.16408 [cs, math]

Attachments:

• storage/MKWKRN4W/Nozaki_Wasa_Yamanaka_2024_Reconfiguration and Enumeration of Optimal Cyclic Ladder Lotteries [Manuscript].pdf - View on Google Drive

Changing Induced Subgraph Isomorphisms Under Extended Reconfiguration Rules

Type: manuscript

Authors: Suga, Tatsuhiro; Suzuki, Akira; Tamura, Yuma; Zhou, Xiao

Date: 2025-01-24

arXiv URL: http://arxiv.org/abs/2501.14450

arXiv ID: 2501.14450 [cs]

Attachments:

• storage/IDB66ZZF/Suga et al_2025_Changing Induced Subgraph Isomorphisms Under Extended Reconfiguration Rules [Manuscript].pdf - View on Google Drive

Basis sequence reconfiguration in the union of matroids

Type: manuscript

Authors: Hanaka, Tesshu; Iwamasa, Yuni; Kobayashi, Yasuaki; Okada, Yuto; Saito, Rin

Date: 2024-09-12

arXiv URL: http://arxiv.org/abs/2409.07848

arXiv ID: 2409.07848 [cs, math]

Attachments:

• storage/C7657K5W/Hanaka et al_2024_Basis sequence reconfiguration in the union of matroids [Manuscript].pdf - View on Google Drive

Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration

Type: manuscript

Authors: Hirahara, Shuichi; Ohsaka, Naoto

Date: 2025-08-01

arXiv URL: http://arxiv.org/abs/2508.00276

arXiv ID: 2508.00276 [cs]

Attachments:

• storage/XQN8MKX5/Hirahara_Ohsaka_2025_Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration [Manuscript].pdf - View on Google Drive

Reconfiguring Proportional Committees

Type: manuscript

Authors: Dong, Chris; Frank, Fabian; Peters, Jannik; Suksompong, Warut

Date: 2025-04-21

arXiv URL: http://arxiv.org/abs/2504.15157

arXiv ID: 2504.15157 [cs]

Attachments:

• storage/QMRUYJLF/Dong et al_2025_Reconfiguring Proportional Committees [Manuscript].pdf - View on Google Drive

Reconfiguration of vertex colouring and forbidden induced subgraphs

Type: manuscript

Authors: Belavadi, Manoj; Cameron, Kathie; Merkel, Owen

Date: 2022-06-18

arXiv URL: http://arxiv.org/abs/2206.09268

arXiv ID: 2206.09268 [math]

Attachments:

• storage/LR3PIAMD/Belavadi_Cameron_Merkel_2022_Reconfiguration of vertex colouring and forbidden induced subgraphs [Manuscript].pdf - View on Google Drive

5-Coloring Reconfiguration of Planar Graphs with No Short Odd Cycles

Type: manuscript

Authors: Cranston, Daniel W.; Mahmoud, Reem

Date: 2022-08-16

arXiv URL: http://arxiv.org/abs/2208.02228

arXiv ID: 2208.02228 [math]

Attachments:

• storage/PLBURXUK/Cranston_Mahmoud_2022_5-Coloring Reconfiguration of Planar Graphs with No Short Odd Cycles [Manuscript].pdf - View on Google Drive

Eulerian $k$-dominating reconfiguration graphs

Type: manuscript

Authors: Messinger, M. E.; Porter, A.

Date: 2024-04-16

arXiv URL: http://arxiv.org/abs/2404.10962

arXiv ID: 2404.10962 [math]

Attachments:

• storage/287W4PIK/Messinger_Porter_2024_Eulerian $k$-dominating reconfiguration graphs [Manuscript].pdf - View on Google Drive

Redicoloring some classes of circulant tournaments

Type: manuscript

Authors: Cordero-Michel, Narda; Olsen, Mika

Date: 2025-10-06

arXiv URL: http://arxiv.org/abs/2510.04990

arXiv ID: 2510.04990 [math]

Attachments:

• storage/CLPAV8SV/Cordero-Michel_Olsen_2025_Redicoloring some classes of circulant tournaments [Preprint].pdf - View on Google Drive

Reconfiguration of Multisets with Applications to Bin Packing

Type: manuscript

Authors: Kam, Jeffrey; Kamali, Shahin; Miller, Avery; Nishimura, Naomi

Date: 2024-05-09

arXiv URL: http://arxiv.org/abs/2405.05535

arXiv ID: 2405.05535 [cs]

Attachments:

• storage/FICHAPY9/Kam et al_2024_Reconfiguration of Multisets with Applications to Bin Packing [Manuscript].pdf - View on Google Drive

Reconfiguration of List Colourings

Type: manuscript

Authors: Cambie, Stijn; Batenburg, Wouter Cames van; Cranston, Daniel W.; Heuvel, Jan van den; Kang, Ross J.

Date: 2025-05-12

arXiv URL: http://arxiv.org/abs/2505.08020

arXiv ID: 2505.08020 [math]

Attachments:

• storage/X9WSDQTH/Cambie et al_2025_Reconfiguration of List Colourings [Manuscript].pdf - View on Google Drive

Linear recoloring diameter of degenerate chordal graphs and bounded treewidth graphs

Type: manuscript

Authors: Wang, Yichen; Lu, Mei

Date: 2025-11-04

arXiv URL: http://arxiv.org/abs/2509.15456

arXiv ID: 2509.15456 [math]

Attachments:

• storage/MC23UVLJ/Wang_Lu_2025_Linear recoloring diameter of degenerate chordal graphs and bounded treewidth graphs [Manuscript].pdf - View on Google Drive

Generalized Token Graphs

Type: manuscript

Authors: Herrera-Ramirez, C. Amairani; Hoekstra-Mendoza, Teresa I.

Date: 2025-09-01

arXiv URL: http://arxiv.org/abs/2509.01773

arXiv ID: 2509.01773 [math]

Attachments:

• storage/33DG7WZ8/Herrera-Ramirez_Hoekstra-Mendoza_2025_Generalized Token Graphs [Manuscript].pdf - View on Google Drive

Determining a graph from its reconfiguration graph

Type: manuscript

Authors: Berthe, Gaétan; Brosse, Caroline; Hearn, Brian; Heuvel, Jan van den; Hoppenot, Pierre; Pierron, Théo

Date: 2025-04-28

arXiv URL: http://arxiv.org/abs/2504.19783

arXiv ID: 2504.19783 [math]

Attachments:

• storage/A4244RH7/Berthe et al_2025_Determining a graph from its reconfiguration graph [Manuscript].pdf - View on Google Drive

Flipping odd matchings in geometric and combinatorial settings

Type: manuscript

Authors: Aichholzer, Oswin; Brenner, Sofia; Dorfer, Joseph; Hoang, Hung P.; Perz, Daniel; Rieck, Christian; Verciani, Francesco

Date: 2025-08-25

arXiv URL: http://arxiv.org/abs/2508.18457

arXiv ID: 2508.18457 [cs]

Attachments:

• storage/IWFFLXQB/Aichholzer et al_2025_Flipping odd matchings in geometric and combinatorial settings [Manuscript].pdf - View on Google Drive

On the complexity of constrained reconfiguration and motion planning

Type: manuscript

Authors: Bousquet, Nicolas; Sabeh, Remy El; Mouawad, Amer E.; Nishimura, Naomi

Date: 2025-08-28

arXiv URL: http://arxiv.org/abs/2508.13032

arXiv ID: 2508.13032 [cs]

Attachments:

• storage/QTLSVMCU/Bousquet et al_2025_On the complexity of constrained reconfiguration and motion planning [Preprint].pdf - View on Google Drive

List-recoloring of two classes of planar graphs

Type: manuscript

Authors: Pan, Chenran; Wang, Weifan; Liu, Runrun

Date: 2025-10-20

arXiv URL: http://arxiv.org/abs/2510.17628

arXiv ID: 2510.17628 [math]

Attachments:

• storage/SN6B56HX/Pan_Wang_Liu_2025_List-recoloring of two classes of planar graphs [Manuscript].pdf - View on Google Drive

Monotonically Decreasing the Number of Directed 3-Cycles via Edge-Flips?

Type: manuscript

Authors: Bom, David; Unger, Florian; Vogtenhuber, Birgit

Date: 2025-10-26

arXiv URL: http://arxiv.org/abs/2510.22862

arXiv ID: 2510.22862 [math]

Attachments:

• storage/YAYYS76A/Bom_Unger_Vogtenhuber_2025_Monotonically Decreasing the Number of Directed 3-Cycles via Edge-Flips [Preprint].pdf - View on Google Drive

Temporal Graph Reconfiguration for Always-Connected Graphs

Type: manuscript

Authors: Sievers, Paul; Skretas, George; Tennigkeit, Georg

Date: 2025-10-17

arXiv URL: http://arxiv.org/abs/2510.15593

arXiv ID: 2510.15593 [cs]

Attachments:

• storage/WEJKMIS3/Sievers_Skretas_Tennigkeit_2025_Temporal Graph Reconfiguration for Always-Connected Graphs [Manuscript].pdf - View on Google Drive

How to Reconfigure Your Alliances

Type: manuscript

Authors: Fernau, Henning; Mann, Kevin

Date: 2025-09-10

arXiv URL: http://arxiv.org/abs/2509.08798

arXiv ID: 2509.08798 [cs]

Attachments:

• storage/56MC3SAS/Fernau_Mann_2025_How to Reconfigure Your Alliances [Manuscript].pdf - View on Google Drive

Reachability of Independent Sets and Vertex Covers Under Extended Reconfiguration Rules

Type: manuscript

Authors: Hirahara, Shuichi; Ohsaka, Naoto; Suga, Tatsuhiro; Suzuki, Akira; Tamura, Yuma; Zhou, Xiao

Date: 2025-10-28

arXiv URL: http://arxiv.org/abs/2510.24226

arXiv ID: 2510.24226 [cs]

Attachments:

• storage/4ZXKNTHU/Hirahara et al_2025_Reachability of Independent Sets and Vertex Covers Under Extended Reconfiguration Rules [Manuscript].pdf - View on Google Drive

The tape reconfiguration problem and its consequences for dominating set reconfiguration

Type: manuscript

Authors: Bousquet, Nicolas; Deschamps, Quentin; Mary, Arnaud; Mouawad, Amer E.; Pierron, Théo

Date: 2025-05-02

arXiv URL: http://arxiv.org/abs/2505.00988

arXiv ID: 2505.00988 [cs]

Attachments:

• storage/A6EB5G9I/Bousquet et al_2025_The tape reconfiguration problem and its consequences for dominating set reconfiguration [Manuscript].pdf - View on Google Drive

On Algorithmic Meta-Theorems for Solution Discovery: Tractability and Barriers

Type: manuscript

Authors: Bousquet, Nicolas; Mouawad, Amer E.; Maaz, Stephanie; Nishimura, Naomi; Siebertz, Sebastian

Date: 2025-10-20

arXiv URL: http://arxiv.org/abs/2510.17344

arXiv ID: 2510.17344 [cs]

Attachments:

• storage/YT23TIVN/Bousquet et al_2025_On Algorithmic Meta-Theorems for Solution Discovery [Manuscript].pdf - View on Google Drive

Efficient algorithms to solve atom reconfiguration problems. III. The bird and batching algorithms and other parallel implementations on GPUs

Type: manuscript

Authors: Afiouni, Fouad; Sabeh, Remy El; Nishimura, Naomi; Hajj, Izzat El; Mouawad, Amer E.; Cooper, Alexandre

Date: 2025-04-08

arXiv URL: http://arxiv.org/abs/2504.06182

arXiv ID: 2504.06182 [quant-ph]

Attachments:

• storage/QJ4EBUQZ/Afiouni et al_2025_Efficient algorithms to solve atom reconfiguration problems [Manuscript].pdf - View on Google Drive

Parameterized Shortest Path Reconfiguration

Type: manuscript

Authors: Bousquet, Nicolas; Gajjar, Kshitij; Lahiri, Abhiruk; Mouawad, Amer E.

Date: 2024-06-18

arXiv URL: http://arxiv.org/abs/2406.12717

arXiv ID: 2406.12717 [cs, math]

Attachments:

• storage/ZJFM5RDV/Bousquet et al_2024_Parameterized Shortest Path Reconfiguration [Manuscript].pdf - View on Google Drive

The Origami flip graph of the $2\times n$ Miura-ori

Type: manuscript

Authors: Christensen, Lumi; Hull, Thomas C.; O'Neil, Emma; Pappano, Valentina; Ter-Saakov, Natalya; Yang, Kacey

Date: 2025-06-24

arXiv URL: http://arxiv.org/abs/2506.19700

arXiv ID: 2506.19700 [math]

Attachments:

• storage/JXF7HMEL/Christensen et al_2025_The Origami flip graph of the $2-times n$ Miura-ori [Manuscript].pdf - View on Google Drive

Reconfiguration of the Union of Arborescences

Type: manuscript

Authors: Kobayashi, Yusuke; Mahara, Ryoga; Schwarcz, Tamás

Date: 2023-04-25

arXiv URL: http://arxiv.org/abs/2304.13217

arXiv ID: 2304.13217 [cs, math]

Attachments:

• storage/42PLC9BW/Kobayashi_Mahara_Schwarcz_2023_Reconfiguration of the Union of Arborescences [Manuscript].pdf - View on Google Drive

Algorithmic Theory of Qubit Routing

Type: manuscript

Authors: Ito, Takehiro; Kakimura, Naonori; Kamiyama, Naoyuki; Kobayashi, Yusuke; Okamoto, Yoshio

Date: 2023-05-14

arXiv URL: http://arxiv.org/abs/2305.02059

arXiv ID: 2305.02059 [quant-ph]

Attachments:

• storage/WWNU94A6/Ito et al_2023_Algorithmic Theory of Qubit Routing [Manuscript].pdf - View on Google Drive

Short and local transformations between ($\Delta+1$)-colorings

Type: manuscript

Authors: Bousquet, Nicolas; Feuilloley, Laurent; Heinrich, Marc; Rabie, Mikaël

Date: 2022-03-16

arXiv URL: http://arxiv.org/abs/2203.08885

arXiv ID: 2203.08885

Attachments:

• storage/FQLATNRW/Bousquet et al_2022_Short and local transformations between ($-Delta+1$)-colorings [Manuscript].pdf - View on Google Drive

Reconfiguring Multiple Connected Components with Size Multiset Constraints

Type: manuscript

Authors: Nakahata, Yu

Date: 2025-05-12

arXiv URL: http://arxiv.org/abs/2505.07268

arXiv ID: 2505.07268 [cs]

Attachments:

• storage/3GEEFSLC/Nakahata_2025_Reconfiguring Multiple Connected Components with Size Multiset Constraints [Manuscript].pdf - View on Google Drive

Lower bounds for dominating set reconfiguration on sparse (directed) graphs

Type: manuscript

Authors: Dirks, Jona; Vigny, Alexandre

Date: 2025-07-15

arXiv URL: http://arxiv.org/abs/2507.11446

arXiv ID: 2507.11446 [cs]

Attachments:

• storage/XZW5MYQI/Dirks_Vigny_2025_Lower bounds for dominating set reconfiguration on sparse (directed) graphs [Manuscript].pdf - View on Google Drive

A Linear Time Algorithm for Finding Minimum Flip Sequences between Plane Spanning Paths in Convex Point Sets

Type: manuscript

Authors: Aichholzer, Oswin; Dorfer, Joseph

Date: 2025-07-03

arXiv URL: http://arxiv.org/abs/2507.02740

arXiv ID: 2507.02740 [cs]

Attachments:

• storage/WBXIC6KW/Aichholzer_Dorfer_2025_A Linear Time Algorithm for Finding Minimum Flip Sequences between Plane Spanning Paths in Convex Point Sets [Manuscript].pdf - View on Google Drive

PCPP-Based Reconfiguration Inapproximability: Query Complexity vs. Soundness Gap Trade-offs

Type: manuscript

Authors: Guruswami, Venkatesan; Ren, Xuandi; Wu, Kewen

Date: 2025-07-01

arXiv URL: http://arxiv.org/abs/2507.01192

arXiv ID: 2507.01192 [cs]

Attachments:

• storage/8UYK9SDF/Guruswami_Ren_Wu_2025_PCPP-Based Reconfiguration Inapproximability [Manuscript].pdf - View on Google Drive

On the clique covering numbers of Johnson graphs

Type: manuscript

Authors: Jørgensen, Søren Fuglede

Date: 2025-02-20

arXiv URL: http://arxiv.org/abs/2502.15019

arXiv ID: 2502.15019 [math]

Attachments:

• storage/KJBQHUMM/Jørgensen_2025_On the clique covering numbers of Johnson graphs [Manuscript].pdf - View on Google Drive

Characterizing simplex graphs

Type: manuscript

Authors: Xie, Yan-Ting; Xu, Shou-Jun

Date: 2025-03-21

arXiv URL: http://arxiv.org/abs/2503.17160

arXiv ID: 2503.17160 [math]

Attachments:

• storage/SK22SSEQ/Xie_Xu_2025_Characterizing simplex graphs [Manuscript].pdf - View on Google Drive

On the Isomorphism Problem of Cayley Graphs of Graph Products

Type: manuscript

Authors: Mwanza, Marjory

Date: 2025-03-19

arXiv URL: http://arxiv.org/abs/2503.15165

arXiv ID: 2503.15165 [math]

Attachments:

• storage/8CICX4Z7/Mwanza_2025_On the Isomorphism Problem of Cayley Graphs of Graph Products [Manuscript].pdf - View on Google Drive

Token Sliding Reconfiguration on DAGs

Type: manuscript

Authors: Dirks, Jona; Vigny, Alexandre

Date: 2025-04-14

arXiv URL: http://arxiv.org/abs/2504.10671

arXiv ID: 2504.10671 [cs]

Attachments:

• storage/VIXSNSDX/Dirks_Vigny_2025_Token Sliding Reconfiguration on DAGs [Manuscript].pdf - View on Google Drive

The complexity of matroid homomorphism reconfiguration

Type: manuscript

Authors: Heo, Cheolwon; Siggers, Mark

Date: 2025-03-24

arXiv URL: http://arxiv.org/abs/2503.19181

arXiv ID: 2503.19181 [math]

Attachments:

• storage/BGMKB994/Heo_Siggers_2025_The complexity of matroid homomorphism reconfiguration [Manuscript].pdf - View on Google Drive

The Complexity of Distance-$r$ Dominating Set Reconfiguration

Type: manuscript

Authors: Banerjee, Niranka; Hoang, Duc A.

Date: 2023/09/30

arXiv URL: https://arxiv.org/abs/2310.00241v2

Attachments:

• storage/H8MKIMU3/Banerjee_Hoang_2023_The Complexity of Distance-$r$ Dominating Set Reconfiguration [Manuscript].pdf - View on Google Drive

Some results on Vertex Separator Reconfiguration

Type: manuscript

Authors: Gomes, Guilherme C. M.; Nogueira, Sérgio H.; Santos, Vinicius F. dos

Date: 2020-04-22

arXiv URL: http://arxiv.org/abs/2004.10873

arXiv ID: 2004.10873

Attachments:

• storage/3R2VSRNP/Gomes_Nogueira_Santos_2020_Some results on Vertex Separator Reconfiguration [Manuscript].pdf - View on Google Drive

A Recolouring Version of a Conjecture of Reed

Type: manuscript

Authors: Meyer, Lucas De; Legrand-Duchesne, Clément; León, Jared; Planken, Tim; Tamitegama, Youri

Date: 2025-02-14

arXiv URL: http://arxiv.org/abs/2502.10147

arXiv ID: 2502.10147 [math]

Attachments:

• storage/SJEMIE2Z/Meyer et al_2025_A Recolouring Version of a Conjecture of Reed [Manuscript].pdf - View on Google Drive

List recoloring of planar graphs

Type: manuscript

Authors: Chandran, L. Sunil; Gupta, Uttam K.; Pradhan, Dinabandhu

Date: 2022-11-29

arXiv URL: http://arxiv.org/abs/2209.05992

arXiv ID: 2209.05992 [cs, math]

Attachments:

• storage/ZBE4YDSB/Chandran_Gupta_Pradhan_2022_List recoloring of planar graphs [Manuscript].pdf - View on Google Drive

Recoloring some hereditary graph classes

Type: manuscript

Authors: Belavadi, Manoj; Cameron, Kathie

Date: 2023-12-01

arXiv URL: http://arxiv.org/abs/2312.00979

arXiv ID: 2312.00979 [math]

Attachments:

• storage/Y3HZ545Y/Belavadi_Cameron_2023_Recoloring some hereditary graph classes [Manuscript].pdf - View on Google Drive

On Pancyclicity in a Mixed Model for Domination Reconfiguration

Type: manuscript

Authors: Messinger, Margaret-Ellen; Pipes, Logan

Date: 2025-02-24

arXiv URL: http://arxiv.org/abs/2502.17227

arXiv ID: 2502.17227 [math]

Attachments:

• storage/YYGV6HW8/Messinger_Pipes_2025_On Pancyclicity in a Mixed Model for Domination Reconfiguration [Manuscript].pdf - View on Google Drive

Reconfiguration of Digraph Homomorphisms

Type: manuscript

Authors: Lévêque, Benjamin; Mühlenthaler, Moritz; Suzan, Thomas

Date: 2022-05-18

arXiv URL: http://arxiv.org/abs/2205.09210

arXiv ID: 2205.09210 [cs, math]

DOI: 10.48550/arXiv.2205.09210

Attachments:

• storage/KIBUCZ78/Lévêque_Mühlenthaler_Suzan_2022_Reconfiguration of Digraph Homomorphisms [Manuscript].pdf - View on Google Drive

Revisiting Token Sliding on Chordal Graphs

Type: manuscript

Authors: Adak, Rajat; Nanoti, Saraswati Girish; Tale, Prafullkumar

Date: 2025-02-18

arXiv URL: http://arxiv.org/abs/2502.12749

arXiv ID: 2502.12749 [cs]

Attachments:

• storage/E6IWHVVU/Adak_Nanoti_Tale_2025_Revisiting Token Sliding on Chordal Graphs [Manuscript].pdf - View on Google Drive

Computing the Polytope Diameter is Even Harder than NP-hard (Already for Perfect Matchings)

Type: manuscript

Authors: Wulf, Lasse

Date: 2025-02-23

arXiv URL: http://arxiv.org/abs/2502.16398

arXiv ID: 2502.16398 [cs]

Attachments:

• storage/FG4X6V9S/Wulf_2025_Computing the Polytope Diameter is Even Harder than NP-hard (Already for Perfect Matchings) [Manuscript].pdf - View on Google Drive

Flipping Non-Crossing Spanning Trees

Type: manuscript

Authors: Bjerkevik, Håvard Bakke; Kleist, Linda; Ueckerdt, Torsten; Vogtenhuber, Birgit

Date: 2024/10/31

arXiv URL: https://arxiv.org/abs/2410.23809v1

Attachments:

• storage/C2XVK6FH/Bjerkevik et al_2024_Flipping Non-Crossing Spanning Trees [Manuscript].pdf - View on Google Drive

Optimal List Recoloring of Subcubic Graphs and Complete Multipartite Graphs

Type: manuscript

Authors: Meyer, Lucas De

Date: 2025-01-09

arXiv URL: http://arxiv.org/abs/2501.03748

arXiv ID: 2501.03748 [math]

Attachments:

• storage/ZGNEVBET/Meyer_2025_Optimal List Recoloring of Subcubic Graphs and Complete Multipartite Graphs [Manuscript].pdf - View on Google Drive

Reconfiguration of square-tiled surfaces

Type: manuscript

Authors: Delecroix, Vincent; Legrand-Duchesne, Clément

Date: 2025-01-27

arXiv URL: http://arxiv.org/abs/2501.15978

arXiv ID: 2501.15978 [math]

Attachments:

• storage/93Y3MHQT/Delecroix_Legrand-Duchesne_2025_Reconfiguration of square-tiled surfaces [Preprint].pdf - View on Google Drive

On some metric properties of supertoken graphs

Type: manuscript

Authors: Baskoro, E. T.; Dalfó, C.; Fiol, M. A.; Simanjuntak, R.

Date: 2024-12-29

arXiv URL: http://arxiv.org/abs/2412.20558

arXiv ID: 2412.20558 [math]

Attachments:

• storage/3KL3APFW/Baskoro et al_2024_On some metric properties of supertoken graphs [Manuscript].pdf - View on Google Drive

Examining Kempe equivalence via commutative algebra

Type: manuscript

Authors: Ohsugi, Hidefumi; Tsuchiya, Akiyoshi

Date: 2024-01-11

arXiv URL: http://arxiv.org/abs/2401.06027

arXiv ID: 2401.06027 [math]

Attachments:

• storage/LN7YJUU6/Ohsugi_Tsuchiya_2024_Examining Kempe equivalence via commutative algebra [Manuscript].pdf - View on Google Drive

Reconfiguration of Minimum PSD Forcing Sets and Minimum Skew Forcing Sets

Type: manuscript

Authors: Bong, Novi; Flagg, Mary; Hunnell, Mark; Hutchens, John; Moruzzi, Ryan; Schuerger, Houston; Small, Ben

Date: 2025-01-07

arXiv URL: http://arxiv.org/abs/2501.03642

arXiv ID: 2501.03642 [math]

Attachments:

• storage/BKDRR2RH/Bong et al_2025_Reconfiguration of Minimum PSD Forcing Sets and Minimum Skew Forcing Sets [Manuscript].pdf - View on Google Drive

Approximately Optimal Search on a Higher-dimensional Sliding Puzzle

Type: manuscript

Authors: Merleau, Nono SC; O'Malley, Miguel; Roldán, Érika; Mukherjee, Sayan

Date: 2024-12-02

arXiv URL: http://arxiv.org/abs/2412.01937

arXiv ID: 2412.01937 [cs]

Attachments:

• storage/DVRBBRN5/Merleau et al_2024_Approximately Optimal Search on a Higher-dimensional Sliding Puzzle [Manuscript].pdf - View on Google Drive

Horadam cubes

Type: manuscript

Authors: Podrug, Luka

Date: 2024-10-04

arXiv URL: http://arxiv.org/abs/2410.03193

arXiv ID: 2410.03193 [math]

Attachments:

• storage/RPINL58C/Podrug_2024_Horadam cubes [Manuscript].pdf - View on Google Drive

Quantum permutation puzzles with indistinguishable particles

Type: manuscript

Authors: Lordi, Noah; Trank-Greene, Maedee; Kyle, Akira; Combes, Joshua

Date: 2024-10-29

arXiv URL: http://arxiv.org/abs/2410.22287

arXiv ID: 2410.22287 [quant-ph]

Attachments:

• storage/559KEUPM/Lordi et al_2024_Quantum permutation puzzles with indistinguishable particles [Manuscript].pdf - View on Google Drive

On the Algebraic Connectivity of Token Graphs and Graphs under Perturbations

Type: manuscript

Authors: Song, X.; Dalfó, C.; Fiol, M. A.; Zhang, S.

Date: 2024-12-30

arXiv URL: http://arxiv.org/abs/2412.21021

arXiv ID: 2412.21021 [math]

Attachments:

• storage/EHRUNP2H/Song et al_2024_On the Algebraic Connectivity of Token Graphs and Graphs under Perturbations [Manuscript].pdf - View on Google Drive

Reconfiguration of unit squares and disks: PSPACE-hardness in simple settings

Type: manuscript

Authors: Abrahamsen, Mikkel; Buchin, Kevin; Buchin, Maike; Kleist, Linda; Löffler, Maarten; Schlipf, Lena; Schulz, André; Stade, Jack

Date: 2024-12-30

arXiv URL: http://arxiv.org/abs/2412.21017

arXiv ID: 2412.21017 [cs]

Attachments:

• storage/UHGDETQ3/Abrahamsen et al_2024_Reconfiguration of unit squares and disks [Manuscript].pdf - View on Google Drive

Sharp Bounds on Lengths of Linear Recolouring Sequences

Type: manuscript

Authors: Cambie, Stijn; Batenburg, Wouter Cames van; Cranston, Daniel W.

Date: 2024-12-27

arXiv URL: http://arxiv.org/abs/2412.19695

arXiv ID: 2412.19695 [math]

Attachments:

• storage/DHYP8ABZ/Cambie_Batenburg_Cranston_2024_Sharp Bounds on Lengths of Linear Recolouring Sequences [Manuscript].pdf - View on Google Drive

Directed Token Sliding

Type: manuscript

Authors: Banerjee, Niranka; Engels, Christian; Hoang, Duc A.

Date: 2024/11/25

arXiv URL: https://arxiv.org/abs/2411.16149v1

Attachments:

• storage/A629R9FC/Banerjee_Engels_Hoang_2024_Directed Token Sliding [Manuscript].pdf - View on Google Drive

Reconfiguration Using Generalized Token Jumping

Type: manuscript

Authors: Křišťan, Jan Matyáš; Svoboda, Jakub

Date: 2024-11-19

arXiv URL: http://arxiv.org/abs/2411.12582

arXiv ID: 2411.12582

Attachments:

• storage/ALEUBX72/Křišťan_Svoboda_2024_Reconfiguration Using Generalized Token Jumping [Manuscript].pdf - View on Google Drive

Hardness of approximation for ground state problems

Type: manuscript

Authors: Gharibian, Sevag; Hecht, Carsten

Date: 2024-11-07

arXiv URL: http://arxiv.org/abs/2411.04874

arXiv ID: 2411.04874

Attachments:

• storage/H8FGMUTM/Gharibian_Hecht_2024_Hardness of approximation for ground state problems [Manuscript].pdf - View on Google Drive

10-list Recoloring of Planar Graphs

Type: manuscript

Authors: Cranston, Daniel W.

Date: 2024-11-01

arXiv URL: http://arxiv.org/abs/2411.00679

arXiv ID: 2411.00679

Attachments:

• storage/YJNR5GBB/Cranston_2024_10-list Recoloring of Planar Graphs [Manuscript].pdf - View on Google Drive

Reconfiguration graphs for minimal domination sets

Type: manuscript

Authors: Beaton, Iain

Date: 2024/11/04

arXiv URL: https://arxiv.org/abs/2411.02300v1

Attachments:

• storage/6FLJSLKC/Beaton_2024_Reconfiguration graphs for minimal domination sets [Manuscript].pdf - View on Google Drive

PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation

Type: manuscript

Authors: Hearn, Robert A.; Demaine, Erik D.

Date: 2004-11-11

arXiv URL: http://arxiv.org/abs/cs/0205005

arXiv ID: cs/0205005

Attachments:

• storage/6UNY467Q/Hearn_Demaine_2004_PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through the Nondeterministic Constraint Logic Model of Computation [Manuscript].pdf - View on Google Drive

Improved Hardness-of-Approximation for Token Swapping

Type: manuscript

Authors: Hiken, Sam; Wein, Nicole

Date: 2024-10-25

arXiv URL: http://arxiv.org/abs/2410.19638

arXiv ID: 2410.19638

Attachments:

• storage/94Y8B7PE/Hiken_Wein_2024_Improved Hardness-of-Approximation for Token Swapping [Manuscript].pdf - View on Google Drive

A study on token digraphs

Type: manuscript

Authors: Fernandes, Cristina G.; Lintzmayer, Carla N.; Peña, Juan P.; Santos, Giovanne; Trujillo-Negrete, Ana; Zamora, Jose

Date: 2024-10-26

arXiv URL: http://arxiv.org/abs/2410.20189

arXiv ID: 2410.20189

Attachments:

• storage/PG2EPGS4/Fernandes et al_2024_A study on token digraphs [Manuscript].pdf - View on Google Drive

Reconfiguring homomorphisms to reflexive graphs via a simple reduction

Type: manuscript

Authors: Mühlenthaler, Moritz; Siggers, Mark H.; Suzan, Thomas

Date: 2024/10/16

arXiv URL: https://arxiv.org/abs/2410.12687v1

Attachments:

• storage/K4QT42VK/Mühlenthaler_Siggers_Suzan_2024_Reconfiguring homomorphisms to reflexive graphs via a simple reduction [Manuscript].pdf - View on Google Drive

Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration

Type: manuscript

Authors: Hirahara, Shuichi; Ohsaka, Naoto

Date: 2024-02-19

arXiv URL: http://arxiv.org/abs/2402.12645

arXiv ID: 2402.12645 [cs]

Attachments:

• storage/5D9RQ6R3/Hirahara_Ohsaka_2024_Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration [Manuscript].pdf - View on Google Drive

Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration

Type: manuscript

Authors: Hirahara, Shuichi; Ohsaka, Naoto

Date: 2024/2/29

Attachments:

• storage/I25MTXM3/Hirahara_Ohsaka_2024_Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration [Manuscript].pdf - View on Google Drive

Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems

Type: manuscript

Authors: Hirahara, Shuichi; Ohsaka, Naoto

Date: 2024/2/11

Attachments:

• storage/XXLSW455/Hirahara_Ohsaka_2024_Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems [Manuscript].pdf - View on Google Drive

Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems

Type: manuscript

Authors: Hirahara, Shuichi; Ohsaka, Naoto

Date: 2023-12-31

arXiv URL: http://arxiv.org/abs/2401.00474

arXiv ID: 2401.00474 [cs]

Attachments:

• storage/C8AQZ573/Hirahara_Ohsaka_2023_Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems [Manuscript].pdf - View on Google Drive

On finding short reconfiguration sequences between independent sets

Type: manuscript

Authors: Agrawal, Akanksha; Hait, Soumita; Mouawad, Amer E.

Date: 2022-09-12

arXiv URL: http://arxiv.org/abs/2209.05145

arXiv ID: 2209.05145 [cs, math]

Attachments:

• storage/7KVQ5WUP/Agrawal_Hait_Mouawad_2022_On finding short reconfiguration sequences between independent sets [Manuscript].pdf - View on Google Drive

Optimal In-Place Compaction of Sliding Cubes

Type: manuscript

Authors: Kostitsyna, Irina; Ophelders, Tim; Parada, Irene; Peters, Tom; Sonke, Willem; Speckmann, Bettina

Date: 2023/12/22

arXiv URL: https://arxiv.org/abs/2312.15096v1

Attachments:

• storage/RZLPFAVG/Kostitsyna et al_2023_Optimal In-Place Compaction of Sliding Cubes [Manuscript].pdf - View on Google Drive

Reconfigurations of Plane Caterpillars and Paths

Type: manuscript

Authors: Antić, Todor; Quintero, Guillermo Gamboa; Glišić, Jelena

Date: 2024-10-09

arXiv URL: http://arxiv.org/abs/2410.07419

arXiv ID: 2410.07419

Attachments:

• storage/PSL5W38C/Antić_Quintero_Glišić_2024_Reconfigurations of Plane Caterpillars and Paths [Manuscript].pdf - View on Google Drive

Reconfiguration graphs for vertex colorings of $P_5$-free graphs

Type: manuscript

Authors: Lei, Hui; Ma, Yulai; Miao, Zhengke; Shi, Yongtang; Wang, Susu

Date: 2024-09-28

arXiv URL: http://arxiv.org/abs/2409.19368

arXiv ID: 2409.19368

Attachments:

• storage/L8Q7M3R5/Lei et al_2024_Reconfiguration graphs for vertex colorings of $P_5$-free graphs [Manuscript].pdf - View on Google Drive

Kernelization Complexity of Solution Discovery Problems

Type: manuscript

Authors: Grobler, Mario; Maaz, Stephanie; Mouawad, Amer E.; Nishimura, Naomi; Ramamoorthi, Vijayaragunathan; Siebertz, Sebastian

Date: 2024-09-25

arXiv URL: http://arxiv.org/abs/2409.17250

arXiv ID: 2409.17250 [cs, math]

Attachments:

• storage/L96MYP9H/Grobler et al_2024_Kernelization Complexity of Solution Discovery Problems [Manuscript].pdf - View on Google Drive

Finding a reconfiguration sequence between longest increasing subsequences

Type: manuscript

Authors: Aoike, Yuuki; Kiyomi, Masashi; Kobayashi, Yasuaki; Otachi, Yota

Date: 2023-10-02

arXiv URL: http://arxiv.org/abs/2310.01066

arXiv ID: 2310.01066 null

Attachments:

• storage/QLHXKCUM/Aoike et al_2023_Finding a reconfiguration sequence between longest increasing subsequences [Manuscript].pdf - View on Google Drive

Reconfiguration of labeled matchings in triangular grid graphs

Type: manuscript

Authors: Kakimura, Naonori; Mishima, Yuta

Date: 2024-09-18

arXiv URL: http://arxiv.org/abs/2409.11723

arXiv ID: 2409.11723 [cs]

Attachments:

• storage/7X2CUD6P/Kakimura_Mishima_2024_Reconfiguration of labeled matchings in triangular grid graphs [Manuscript].pdf - View on Google Drive

Kempe Classes and Almost Bipartite Graphs

Type: manuscript

Authors: Cranston, Daniel W.; Feghali, Carl

Date: 2023-03-16

arXiv URL: http://arxiv.org/abs/2303.09365

arXiv ID: 2303.09365 [math]

Attachments:

• storage/9BAXFE5A/Cranston_Feghali_2023_Kempe Classes and Almost Bipartite Graphs [Manuscript].pdf - View on Google Drive

Dominating Set Reconfiguration with Answer Set Programming

Type: manuscript

Authors: Kato, Masato; Schaub, Torsten; Soh, Takehide; Tamura, Naoyuki; Banbara, Mutsunori

Date: 2024-08-14

arXiv URL: http://arxiv.org/abs/2408.07510

arXiv ID: 2408.07510 [cs]

Attachments:

• storage/VU2EB6NE/Kato et al_2024_Dominating Set Reconfiguration with Answer Set Programming [Manuscript].pdf - View on Google Drive

A survey on the parameterized complexity of the independent set and (connected) dominating set reconfiguration problems

Type: manuscript

Authors: Bousquet, Nicolas; Mouawad, Amer E.; Nishimura, Naomi; Siebertz, Sebastian

Date: 2022/04/22

arXiv URL: https://arxiv.org/abs/2204.10526v1

arXiv ID: 2204.10526

Attachments:

• storage/5G7FVXY7/Bousquet et al_2022_A survey on the parameterized complexity of the independent set and (connected) dominating set reconfiguration problems [Manuscript].pdf - View on Google Drive

A simple quadratic kernel for Token Jumping on surfaces

Type: manuscript

Authors: Cranston, Daniel W.; Mühlenthaler, Moritz; Peyrille, Benjamin

Date: 2024-08-08

arXiv URL: http://arxiv.org/abs/2408.04743

arXiv ID: 2408.04743 [cs]

Attachments:

• storage/LENBQ6J8/Cranston_Mühlenthaler_Peyrille_2024_A simple quadratic kernel for Token Jumping on surfaces [Manuscript].pdf - View on Google Drive

On the Automorphisms of Token Graphs Generated by $2$-cuts with the Same Neighbours

Type: manuscript

Authors: Fabila-Monroy, Ruy; Gómez-Galicia, Sergio Gerardo; Gregorio-Longino, Daniel; Hoekstra-Mendoza, Teresa I.; Trujillo-Negrete, Ana

Date: 2024-08-07

arXiv URL: http://arxiv.org/abs/2408.04059

arXiv ID: 2408.04059 [math]

Attachments:

• storage/2CUZ8UR3/Fabila-Monroy et al_2024_On the Automorphisms of Token Graphs Generated by $2$-cuts with the Same Neighbours [Manuscript].pdf - View on Google Drive

Independent Set Reconfiguration Under Bounded-Hop Token

Type: manuscript

Authors: Hatano, Hiroki; Kitamura, Naoki; Izumi, Taisuke; Ito, Takehiro; Masuzawa, Toshimitsu

Date: 2024-07-16

arXiv URL: http://arxiv.org/abs/2407.11768

arXiv ID: 2407.11768 [cs]

Attachments:

• storage/8Z2EG4ZZ/Hatano et al_2024_Independent Set Reconfiguration Under Bounded-Hop Token [Manuscript].pdf - View on Google Drive

Reconfiguration of Independent Transversals

Type: manuscript

Authors: Buys, Pjotr; Kang, Ross J.; Ozeki, Kenta

Date: 2024/07/05

arXiv URL: https://arxiv.org/abs/2407.04367v1

Attachments:

• storage/MHQS67YH/Buys_Kang_Ozeki_2024_Reconfiguration of Independent Transversals [Manuscript].pdf - View on Google Drive

A Note On Acyclic Token Sliding Reconfiguration Graphs of Independent Sets

Type: manuscript

Authors: Avis, David; Hoang, Duc A.

Date: 2023-01-01

arXiv URL: http://arxiv.org/abs/2301.00317

arXiv ID: 2301.00317 [cs, math]

Attachments:

• storage/XHMWWKRE/Avis_Hoang_2023_A Note On Acyclic Token Sliding Reconfiguration Graphs of Independent Sets [Manuscript].pdf - View on Google Drive

Further Connectivity Results on Plane Spanning Path Reconfiguration

Type: manuscript

Authors: Boucard, Valentino; da Fonseca, Guilherme D.; Rivier, Bastien

Date: 2024-06-28

arXiv URL: http://arxiv.org/abs/2407.00244

arXiv ID: 2407.00244 [cs]

Attachments:

• storage/A99XWTZP/Boucard_da Fonseca_Rivier_2024_Further Connectivity Results on Plane Spanning Path Reconfiguration [Manuscript].pdf - View on Google Drive

Reconfiguration of plane trees in convex geometric graphs

Type: manuscript

Authors: Bousquet, Nicolas; De Meyer, Lucas; Pierron, Théo; Wesolek, Alexandra

Date: 2023-10-31

arXiv URL: http://arxiv.org/abs/2310.18518

arXiv ID: 2310.18518 [cs]

Attachments:

• storage/JQ7AGMNE/Bousquet et al_2023_Reconfiguration of plane trees in convex geometric graphs [Manuscript].pdf - View on Google Drive

Structural and Combinatorial Properties of 2-swap Word Permutation Graphs

Type: manuscript

Authors: Adamson, Duncan; Flaherty, Nathan; Potapov, Igor; Spirakis, Paul G.

Date: 2024-06-27

arXiv URL: http://arxiv.org/abs/2307.01648

arXiv ID: 2307.01648 [cs, math]

Attachments:

• storage/Z2MGRN78/Adamson et al_2024_Structural and Combinatorial Properties of 2-swap Word Permutation Graphs [Manuscript].pdf - View on Google Drive

On the Longest Flip Sequence to Untangle Segments in the Plane

Type: manuscript

Authors: da Fonseca, Guilherme D.; Gerard, Yan; Rivier, Bastien

Date: 2023-03-17

arXiv URL: http://arxiv.org/abs/2210.12036

arXiv ID: 2210.12036 [cs]

Attachments:

• storage/D9N8HVPF/da Fonseca_Gerard_Rivier_2023_On the Longest Flip Sequence to Untangle Segments in the Plane [Manuscript].pdf - View on Google Drive

On the Complexity of Distance-$d$ Independent Set Reconfiguration

Type: manuscript

Authors: Hoang, Duc A.

Date: 2022-08-15

arXiv URL: http://arxiv.org/abs/2208.07199

arXiv ID: 2208.07199 [cs, math]

Attachments:

• storage/U9GEWDR2/Hoang_2022_On the Complexity of Distance-$d$ Independent Set Reconfiguration [Manuscript].pdf - View on Google Drive

Redicolouring digraphs: directed treewidth and cycle-degeneracy

Type: manuscript

Authors: Nisse, Nicolas; Picasarri-Arrieta, Lucas; Sau, Ignasi

Date: 2024-05-07

arXiv URL: http://arxiv.org/abs/2307.06700

arXiv ID: 2307.06700 [cs, math]

Attachments:

• storage/SS7EEEAP/Nisse_Picasarri-Arrieta_Sau_2024_Redicolouring digraphs - directed treewidth and cycle-degeneracy [Manuscript].pdf - View on Google Drive

TAR reconfiguration for vertex set parameters

Type: manuscript

Authors: Curtis, Bryan A.; Flagg, Mary; Hogben, Leslie

Date: 2024/06/08

arXiv URL: https://arxiv.org/abs/2406.05509v1

Attachments:

• storage/ZJC447U9/Curtis_Flagg_Hogben_2024_TAR reconfiguration for vertex set parameters [Manuscript].pdf - View on Google Drive

Flips in colorful triangulations

Type: manuscript

Authors: Acharya, Rohan; Mütze, Torsten; Verciani, Francesco

Date: 2024-06-06

arXiv URL: http://arxiv.org/abs/2406.03783

arXiv ID: 2406.03783 [cs, math]

Attachments:

• storage/HZFV4JAX/Acharya_Mütze_Verciani_2024_Flips in colorful triangulations [Preprint].pdf - View on Google Drive

The Clique Structure of Johnson Graphs

Type: manuscript

Authors: Shuldiner, Pavel; Oldford, R. Wayne

Date: 2022-08-26

arXiv URL: http://arxiv.org/abs/2208.12710

arXiv ID: 2208.12710 [math]

Attachments:

• storage/JTFWRVK2/Shuldiner_Oldford_2022_The Clique Structure of Johnson Graphs [Manuscript].pdf - View on Google Drive

Recoloring via modular decomposition

Type: manuscript

Authors: Belavadi, Manoj; Cameron, Kathie; Sintiari, Ni Luh Dewi

Date: 2024-05-10

arXiv URL: http://arxiv.org/abs/2405.06446

arXiv ID: 2405.06446 [cs, math]

Attachments:

• storage/72SBRVQT/Belavadi_Cameron_Sintiari_2024_Recoloring via modular decomposition [Manuscript].pdf - View on Google Drive

Distance Recoloring

Type: manuscript

Authors: Banerjee, Niranka; Engels, Christian; Hoang, Duc A.

Date: 2024-05-02

arXiv URL: http://arxiv.org/abs/2402.12705

arXiv ID: 2402.12705 [cs]

Attachments:

• storage/XLLEIRFL/Banerjee_Engels_Hoang_2024_Distance Recoloring [Manuscript].pdf - View on Google Drive

A note on graphs of $k$-colourings

Type: manuscript

Authors: Hogan, Emma; Scott, Alex; Tamitegama, Youri; Tan, Jane

Date: 2024-02-29

arXiv URL: http://arxiv.org/abs/2402.04237

arXiv ID: 2402.04237 [math]

Attachments:

• storage/UDI6D4P7/Hogan et al_2024_A note on graphs of $k$-colourings [Manuscript].pdf - View on Google Drive

A note on graphs of k-colourings

Type: manuscript

Authors: Hogan, Emma; Scott, Alex; Tamitegama, Youri; Tan, Jane

Date: 2024-04-03

Attachments:

• storage/BBYBYE2F/Hogan et al_2024_A note on graphs of k-colourings [Manuscript].pdf - View on Google Drive

On two algebras of token graphs

Type: manuscript

Authors: Reyes, M. A.; Dalfó, C.; Fiol, M. A.

Date: 2024-03-27

arXiv URL: http://arxiv.org/abs/2403.18800

arXiv ID: 2403.18800 [math]

Attachments:

• storage/ALSJ36Q9/Reyes_Dalfó_Fiol_2024_On two algebras of token graphs [Manuscript].pdf - View on Google Drive

A general method to find the spectrum and eigenspaces of the $k$-token of a cycle, and 2-token through continuous fractions

Type: manuscript

Authors: Reyes, M. A.; Dalfó, C.; Fiol, M. A.; Messegué, A.

Date: 2024-03-29

arXiv URL: http://arxiv.org/abs/2403.20148

arXiv ID: 2403.20148 [math]

Attachments:

• storage/QN6T3ZBF/Reyes et al_2024_A general method to find the spectrum and eigenspaces of the $k$-token of a cycle, and 2-token through continuous fractions [Manuscript].pdf - View on Google Drive

Token graphs of Cayley graphs as lifts

Type: manuscript

Authors: Dalfó, C.; Fiol, M. A.; Pavlíková, S.; Širáň, J.

Date: 2024-04-02

arXiv URL: http://arxiv.org/abs/2404.02122

arXiv ID: 2404.02122 [math]

Attachments:

• storage/9LWLN7LY/Dalfó et al_2024_Token graphs of Cayley graphs as lifts [Manuscript].pdf - View on Google Drive

The rotation distance of brooms

Type: manuscript

Authors: Cardinal, Jean; Pournin, Lionel; Valencia-Pabon, Mario

Date: 05/2024

arXiv URL: http://arxiv.org/abs/2211.07984

arXiv ID: 2211.07984 [math]

Attachments:

• storage/FC53BCRQ/Cardinal_Pournin_Valencia-Pabon_2024_The rotation distance of brooms [Manuscript].pdf - View on Google Drive

Flip Graphs of Pseudo-Triangulations With Face Degree at Most 4

Type: manuscript

Authors: Löffler, Maarten; Mchedlidze, Tamara; Orden, David; Tkadlec, Josef; Wulms, Jules

Date: 2024-02-19

arXiv URL: http://arxiv.org/abs/2402.12357

arXiv ID: 2402.12357 [cs]

Attachments:

• storage/Z552QK8B/Löffler et al_2024_Flip Graphs of Pseudo-Triangulations With Face Degree at Most 4 [Preprint].pdf - View on Google Drive

Flip graphs of coloured triangulations of convex polygons

Type: manuscript

Authors: Baur, Karin; Bergerova, Diana; Voon, Jenni; Xu, Lejie

Date: 2024-02-09

arXiv URL: http://arxiv.org/abs/2402.06546

arXiv ID: 2402.06546 [math]

Attachments:

• storage/TGH7KKCL/Baur et al_2024_Flip graphs of coloured triangulations of convex polygons [Preprint].pdf - View on Google Drive

On token signed graphs

Type: manuscript

Authors: Dalfó, C.; Fiol, M. A.; Steffen, E.

Date: 2024-03-05

arXiv URL: http://arxiv.org/abs/2403.02924

arXiv ID: 2403.02924 [math]

Attachments:

• storage/9QJZLBJ3/Dalfó_Fiol_Steffen_2024_On token signed graphs [Manuscript].pdf - View on Google Drive

Short Flip Sequences to Untangle Segments in the Plane

Type: manuscript

Authors: da Fonseca, Guilherme D.; Gerard, Yan; Rivier, Bastien

Date: 2023-07-24

arXiv URL: http://arxiv.org/abs/2307.00853

arXiv ID: 2307.00853 [cs]

Attachments:

• storage/FRTP3JI9/da Fonseca_Gerard_Rivier_2023_Short Flip Sequences to Untangle Segments in the Plane [Manuscript].pdf - View on Google Drive

On the Treewidth of Token and Johnson Graphs

Type: manuscript

Authors: Fabila-Monroy, Ruy; Gómez-Galicia, Sergio Gerardo; Hernández-Cruz, César; Trujillo-Negrete, Ana Laura

Date: 2024-02-27

arXiv URL: http://arxiv.org/abs/2402.17962

arXiv ID: 2402.17962 [math]

Attachments:

• storage/RJ7B9XL5/Fabila-Monroy et al_2024_On the Treewidth of Token and Johnson Graphs [Manuscript].pdf - View on Google Drive