Zotero Collection: Reconfiguration - 2025-10-26

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

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

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

Parameterised algorithms for temporal reconfiguration problems

Type: manuscript

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

Date: 2025-02-17

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

arXiv ID: 2502.11961 [cs]

Attachments:

• storage/LWS5HNUI/Davot_Enright_Larios-Jones_2025_Parameterised algorithms for temporal reconfiguration problems [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

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

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

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

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

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

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/TVI2JYG9/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

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

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

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

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

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

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

Asymptotic Inapproximability of Reconfiguration Problems: Maxmin $k$-Cut and Maxmin E$k$-SAT

Type: manuscript

Authors: Hirahara, Shuichi; Ohsaka, Naoto

Date: 2024-10-04

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

arXiv ID: 2410.03416

Attachments:

• storage/WY8N7ZKV/Hirahara_Ohsaka_2024_Asymptotic Inapproximability of Reconfiguration Problems [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

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

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

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

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

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

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

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

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/4QTBUA35/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

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

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 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: S., Karthik C.; Manurangsi, Pasin

Date: 2023/12/28

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

Attachments:

• storage/TLGGZ8DY/S._Manurangsi_2023_On Inapproximability of Reconfiguration Problems [Manuscript].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

Tight Inapproximability of Target Set Reconfiguration

Type: manuscript

Authors: Ohsaka, Naoto

Date: 2024-02-22

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

arXiv ID: 2402.15076 [cs]

Attachments:

• storage/AN8YLALQ/Ohsaka_2024_Tight Inapproximability of Target Set Reconfiguration [Manuscript].pdf - View on Google Drive

Alphabet Reduction for Reconfiguration Problems

Type: manuscript

Authors: Ohsaka, Naoto

Date: 2024-02-16

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

arXiv ID: 2402.10627 [cs]

Attachments:

• storage/L54VBM9D/Ohsaka_2024_Alphabet Reduction for Reconfiguration Problems [Manuscript].pdf - View on Google Drive

Pairwise Rearrangement is Fixed-Parameter Tractable in the Single Cut-and-Join Model

Type: manuscript

Authors: Bailey, Lora; Blake, Heather Smith; Cochran, Garner; Fox, Nathan; Levet, Michael; Mahmoud, Reem; Singgih, Inne; Stadnyk, Grace; Wiedemann, Alexander

Date: 2024-02-02

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

arXiv ID: 2402.01942 [cs, math, q-bio]

Attachments:

• storage/ERICUK4Y/Bailey et al_2024_Pairwise Rearrangement is Fixed-Parameter Tractable in the Single Cut-and-Join Model [Manuscript].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

Counting subgraphs of coloring graphs

Type: manuscript

Authors: Asgarli, Shamil; Krehbiel, Sara; Levinson, Howard W.; Russell, Heather M.

Date: 2024-01-23

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

arXiv ID: 2401.12883 [math]

Attachments:

• storage/WD63L64Y/Asgarli et al_2024_Counting subgraphs of coloring graphs [Manuscript].pdf - View on Google Drive

Token sliding on graphs of girth five

Type: manuscript

Authors: Bartier, Valentin; Bousquet, Nicolas; Hanna, Jihad; Mouawad, Amer E.; Siebertz, Sebastian

Date: 2022-05-02

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

arXiv ID: 2205.01009

Attachments:

• storage/PUB83PUB/Bartier et al_2022_Token sliding on graphs of girth five [Manuscript].pdf - View on Google Drive

Token Jumping in Planar Graphs has Linear Sized Kernels

Type: manuscript

Authors: Cranston, Daniel W.

Date: 2024-01-17

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

arXiv ID: 2401.09543 [cs]

Attachments:

• storage/9JUQ28G7/Cranston_2024_Token Jumping in Planar Graphs has Linear Sized Kernels [Manuscript].pdf - View on Google Drive

Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement

Type: manuscript

Authors: Gharibian, Sevag; Rudolph, Dorian

Date: 2022-06-10

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

arXiv ID: 2206.05243 [quant-ph]

Attachments:

• storage/WRBCA6HR/Gharibian_Rudolph_2022_Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement [Manuscript].pdf - View on Google Drive

A Note on the Complexity of Graph Recoloring

Type: manuscript

Authors: Bousquet, Nicolas

Date: 2024/01/05

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

Attachments:

• storage/8HT9EARY/Bousquet_2024_A Note on the Complexity of Graph Recoloring [Web Page].pdf - View on Google Drive

Flip Graph Connectivity for Arrangements of Pseudolines and Pseudocircles

Type: manuscript

Authors: Radtke, Yan Alves; Felsner, Stefan; Obenaus, Johannes; Roch, Sandro; Scheucher, Manfred; Vogtenhuber, Birgit

Date: 2023-10-30

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

arXiv ID: 2310.19711 [cs, math]

Attachments:

• storage/IHINCWXU/Radtke et al_2023_Flip Graph Connectivity for Arrangements of Pseudolines and Pseudocircles [Manuscript].pdf - View on Google Drive

Gap Amplification for Reconfiguration Problems

Type: manuscript

Authors: Ohsaka, Naoto

Date: 2023-10-21

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

arXiv ID: 2310.14160 [cs]

Attachments:

• storage/HEG7LLIA/Ohsaka_2023_Gap Amplification for Reconfiguration Problems [Manuscript].pdf - View on Google Drive

Shortest Dominating Set Reconfiguration under Token Sliding

Type: manuscript

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

Date: 2023-07-20

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

arXiv ID: 2307.10847 [cs, math]

Attachments:

• storage/HIZK3NQ4/Křišťan_Svoboda_2023_Shortest Dominating Set Reconfiguration under Token Sliding [Manuscript].pdf - View on Google Drive

On Computing Makespan-Optimal Solutions for Generalized Sliding-Tile Puzzles

Type: manuscript

Authors: Gozon, Marcus; Yu, Jingjin

Date: 2023/12/18

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

Attachments:

• storage/MTTBG36L/Gozon_Yu_2023_On Computing Makespan-Optimal Solutions for Generalized Sliding-Tile Puzzles [Manuscript].pdf - View on Google Drive

Well-forced graphs

Type: manuscript

Authors: Grood, Cheryl; Haas, Ruth; Jacob, Bonnie; King, Erika; Nasserasr, Shahla

Date: 2023/12/21

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

Attachments:

• storage/F67IC5XJ/Grood et al_2023_Well-forced graphs [Manuscript].pdf - View on Google Drive

Reachability of Fair Allocations via Sequential Exchanges

Type: manuscript

Authors: Igarashi, Ayumi; Kamiyama, Naoyuki; Suksompong, Warut; Yuen, Sheung Man

Date: 2023-12-12

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

arXiv ID: 2312.07241 [cs]

Attachments:

• storage/2CKSMBX4/Igarashi et al_2023_Reachability of Fair Allocations via Sequential Exchanges [Preprint].pdf - View on Google Drive

Minimum Separator Reconfiguration

Type: manuscript

Authors: Gomes, Guilherme C. M.; Legrand-Duchesne, Clément; Mahmoud, Reem; Mouawad, Amer E.; Okamoto, Yoshio; Santos, Vinicius F. dos; van der Zanden, Tom C.

Date: 2023/07/15

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

Attachments:

• storage/F57F4JVU/Gomes et al_2023_Minimum Separator Reconfiguration [Manuscript].pdf - View on Google Drive

Digraph redicolouring

Type: manuscript

Authors: Bousquet, Nicolas; Havet, Frédéric; Nisse, Nicolas; Picasarri-Arrieta, Lucas; Reinald, Amadeus

Date: 2023-10-02

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

arXiv ID: 2301.03417 [cs, math]

Attachments:

• storage/MVK2FAIT/Bousquet et al_2023_Digraph redicolouring [Manuscript].pdf - View on Google Drive

On a recolouring version of Hadwiger's conjecture

Type: manuscript

Authors: Bonamy, Marthe; Heinrich, Marc; Legrand-Duchesne, Clément; Narboni, Jonathan

Date: 2021-03-19

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

arXiv ID: 2103.10684

Attachments:

• storage/75RJ3CMV/Bonamy et al_2021_On a recolouring version of Hadwiger's conjecture [Manuscript].pdf - View on Google Drive

Computational Complexity of Jumping Block Puzzles

Type: manuscript

Authors: Kanzaki, Masaaki; Otachi, Yota; Uehara, Ryuhei

Date: 2021-09-05

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

arXiv ID: 2109.02213

Attachments:

• storage/7NM6CT4W/Kanzaki_Otachi_Uehara_2021_Computational Complexity of Jumping Block Puzzles [Manuscript].pdf - View on Google Drive

On Solution Discovery via Reconfiguration

Type: manuscript

Authors: Fellows, Michael R.; Grobler, Mario; Megow, Nicole; Mouawad, Amer E.; Ramamoorthi, Vijayaragunathan; Rosamond, Frances A.; Schmand, Daniel; Siebertz, Sebastian

Date: 2023/04/27

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

Attachments:

• storage/ZAM3LG7N/Fellows et al_2023_On Solution Discovery via Reconfiguration [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

On Hamilton cycles in graphs defined by intersecting set systems

Type: manuscript

Authors: Mütze, Torsten

Date: 2023-11-14

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

arXiv ID: 2311.08521 [math]

Attachments:

• storage/NSL47HJM/Mütze_2023_On Hamilton cycles in graphs defined by intersecting set systems [Manuscript].pdf - View on Google Drive

Shortest paths on polymatroids and hypergraphic polytopes

Type: manuscript

Authors: Cardinal, Jean; Steiner, Raphael

Date: 2023-11-01

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

arXiv ID: 2311.00779 [cs, math]

Attachments:

• storage/4KHDAMSD/Cardinal_Steiner_2023_Shortest paths on polymatroids and hypergraphic polytopes [Manuscript].pdf - View on Google Drive

Strengthening the Directed Brooks' Theorem for oriented graphs and consequences on digraph redicolouring

Type: manuscript

Authors: Picasarri-Arrieta, Lucas

Date: 2023-05-25

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

arXiv ID: 2301.04881 [cs, math]

Attachments:

• storage/2I45TSNQ/Picasarri-Arrieta_2023_Strengthening the Directed Brooks' Theorem for oriented graphs and consequences on digraph redicolouring [Manuscript].pdf - View on Google Drive

Traversability, Reconfiguration, and Reachability in the Gadget Framework

Type: manuscript

Authors: Ani, Joshua; Demaine, Erik; Diomidov, Yevhenii; Hendrickson, Dylan; Lynch, Jayson

Date: 2022/04/01

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

Attachments:

• storage/WKTBW4A3/Ani et al_2022_Traversability, Reconfiguration, and Reachability in the Gadget Framework [Manuscript].pdf - View on Google Drive

Mixing is hard for triangle-free reflexive graphs

Type: manuscript

Authors: Kim, Hyobeen; Lee, Jae-baek; Siggers, Mark

Date: 2023-07-31

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

arXiv ID: 2207.03632 [math]

Attachments:

• storage/QMV7TBGT/Kim_Lee_Siggers_2023_Mixing is hard for triangle-free reflexive graphs [Manuscript].pdf - View on Google Drive

On the spectra of token graphs of cycles and other graphs

Type: manuscript

Authors: Reyes, Mónica A.; Dalfó, Cristina; Fiol, Miquel Àngel; Messegué, Arnau

Date: 2023-09-13

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

arXiv ID: 2309.07089 [math]

Attachments:

• storage/DPBAC8IX/Reyes et al_2023_On the spectra of token graphs of cycles and other graphs [Manuscript].pdf - View on Google Drive

On the spectra and spectral radii of token graphs

Type: manuscript

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

Date: 2023-10-25

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

arXiv ID: 2310.16929 [math]

Attachments:

• storage/BVI3I3GU/Reyes_Dalfó_Fiol_2023_On the spectra and spectral radii of token graphs [Manuscript].pdf - View on Google Drive

Core Challenge 2023: Solver and Graph Descriptions

Type: manuscript

Authors: Soh, Takehide; Okamoto, Yoshio; Ito, Takehiro

Date: 2023-10-26

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

arXiv ID: 2310.17136 [cs]

Attachments:

• storage/6CZSIDHW/Soh_Okamoto_Ito_2023_Core Challenge 2023 - Solver and Graph Descriptions [Manuscript].pdf - View on Google Drive

Parameterized Complexities of Dominating and Independent Set Reconfiguration

Type: manuscript

Authors: Bodlaender, Hans L.; Groenland, Carla; Swennenhuis, Céline M. F.

Date: 2023-10-23

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

arXiv ID: 2106.15907 [cs]

Attachments:

• storage/UEK829J8/Bodlaender_Groenland_Swennenhuis_2023_Parameterized Complexities of Dominating and Independent Set Reconfiguration [Manuscript].pdf - View on Google Drive

On Reachable Assignments under Dichotomous Preferences

Type: manuscript

Authors: Ito, Takehiro; Kakimura, Naonori; Kamiyama, Naoyuki; Kobayashi, Yusuke; Nozaki, Yuta; Okamoto, Yoshio; Ozeki, Kenta

Date: 2022-09-21

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

arXiv ID: 2209.10262 [cs, math]

Attachments:

• storage/5AWQWP32/Ito et al_2022_On Reachable Assignments under Dichotomous Preferences [Manuscript].pdf - View on Google Drive

Optimally Reconfiguring List and Correspondence Colourings

Type: manuscript

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

Date: 01/2024

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

arXiv ID: 2204.07928 [cs, math]

Attachments:

• storage/I6KCAFK9/Cambie_van Batenburg_Cranston_2024_Optimally Reconfiguring List and Correspondence Colourings [Manuscript].pdf - View on Google Drive

The Hamiltonian Path Graph is Connected for Simple $s,t$ Paths in Rectangular Grid Graphs

Type: manuscript

Authors: Nishat, Rahnuma Islam; Srinivasan, Venkatesh; Whitesides, Sue

Date: 2022-05-16

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

arXiv ID: 2205.08025 [cs]

DOI: 10.48550/arXiv.2205.08025

Attachments:

• storage/3QJMEZT3/Nishat_Srinivasan_Whitesides_2022_The Hamiltonian Path Graph is Connected for Simple $s,t$ Paths in Rectangular Grid Graphs [Manuscript].pdf - View on Google Drive

Reconfiguration of Time-Respecting Arborescences

Type: manuscript

Authors: Ito, Takehiro; Iwamasa, Yuni; Kamiyama, Naoyuki; Kobayashi, Yasuaki; Kobayashi, Yusuke; Maezawa, Shun-ichi; Suzuki, Akira

Date: 2023-06-27

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

arXiv ID: 2305.07262 [cs, math]

Attachments:

• storage/Z6K8NX8J/Ito et al_2023_Reconfiguration of Time-Respecting Arborescences [Manuscript].pdf - View on Google Drive

A Lower Bound on the Diameter of the Flip Graph

Type: manuscript

Authors: Frati, Fabrizio

Date: 2015-08-14

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

arXiv ID: 1508.03473 [cs, math]

Attachments:

• storage/G96SW9EH/Frati_2015_A Lower Bound on the Diameter of the Flip Graph [Manuscript].pdf - View on Google Drive

Inapproximability of shortest paths on perfect matching polytopes

Type: manuscript

Authors: Cardinal, Jean; Steiner, Raphael

Date: 2022-10-26

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

arXiv ID: 2210.14608 [cs, math]

Attachments:

• storage/UTNBDRJF/Cardinal_Steiner_2022_Inapproximability of shortest paths on perfect matching polytopes [Manuscript].pdf - View on Google Drive

Bounded Combinatorial Reconfiguration with Answer Set Programming

Type: manuscript

Authors: Yamada, Yuya; Banbara, Mutsunori; Inoue, Katsumi; Schaub, Torsten

Date: 2023-07-20

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

arXiv ID: 2307.10688 [cs]

Attachments:

• storage/VZSEGWDF/Yamada et al_2023_Bounded Combinatorial Reconfiguration with Answer Set Programming [Manuscript].pdf - View on Google Drive

On the $n$-dominating graph of specific graphs

Type: manuscript

Authors: Alikhani, Saeid; Fatehi, Davood

Date: 2015-02-27

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

arXiv ID: 1410.1169 [math]

Attachments:

• storage/Z9ZFRMHF/Alikhani_Fatehi_2015_On the $n$-dominating graph of specific graphs [Manuscript].pdf - View on Google Drive

Some bounds on the Laplacian eigenvalues of token graphs

Type: manuscript

Authors: Dalfó, Cristina; Fiol, Miquel Àngel; Messegué, Arnau

Date: 2023-09-16

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

arXiv ID: 2309.09041 [math]

Attachments:

• storage/INKILQLA/Dalfó_Fiol_Messegué_2023_Some bounds on the Laplacian eigenvalues of token graphs [Manuscript].pdf - View on Google Drive

Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space

Type: manuscript

Authors: Bodlaender, Hans L.; Groenland, Carla; Nederlof, Jesper; Swennenhuis, Céline M. F.

Date: 2021-05-31

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

arXiv ID: 2105.14882 [cs]

Attachments:

• storage/HHVMYTBR/Bodlaender et al_2021_Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space [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

Kempe Equivalent List Edge-Colorings of Planar Graphs

Type: manuscript

Authors: Cranston, Daniel W.

Date: 2021/10/12

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

Attachments:

• storage/2WAC6QSH/Cranston_2021_Kempe Equivalent List Edge-Colorings of Planar Graphs [Manuscript].pdf - View on Google Drive

On dominating graph of graphs, median graphs and partial cubes, and graphs in which complement of every minimal dominating set is minimal dominating

Type: manuscript

Authors: Mofidi, Alireza

Date: 2022-12-08

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

arXiv ID: 2212.04570 [math]

Attachments:

• storage/MX4JJNM5/Mofidi_2022_On dominating graph of graphs, median graphs and partial cubes, and graphs in which complement of every minimal dominating set is minimal dominating [Manuscript].pdf - View on Google Drive

On the algebraic connectivity of token graphs

Type: manuscript

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

Date: 2022-09-02

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

arXiv ID: 2209.01030 [math]

Attachments:

• storage/7J4M882D/Dalfó_Fiol_2022_On the algebraic connectivity of token graphs [Manuscript].pdf - View on Google Drive

Higher-dimensional cubical sliding puzzles

Type: manuscript

Authors: Beyer, Moritz; Mereta, Stefano; Roldán, Érika; Voran, Peter

Date: 2023-07-26

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

arXiv ID: 2307.14143 [cs, math]

Attachments:

• storage/CQXWZ25T/Beyer et al_2023_Higher-dimensional cubical sliding puzzles [Manuscript].pdf - View on Google Drive

ZDD-Based Algorithmic Framework for Solving Shortest Reconfiguration Problems

Type: manuscript

Authors: Ito, Takehiro; Kawahara, Jun; Nakahata, Yu; Soh, Takehide; Suzuki, Akira; Teruyama, Junichi; Toda, Takahisa

Date: 2022-07-28

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

arXiv ID: 2207.13959 [cs]

Attachments:

• storage/4EIVQNFP/Ito et al_2022_ZDD-Based Algorithmic Framework for Solving Shortest Reconfiguration Problems [Manuscript].pdf - View on Google Drive

Reconfiguration of Polygonal Subdivisions via Recombination

Type: manuscript

Authors: Akitaya, Hugo A.; Gonczi, Andrei; Souvaine, Diane L.; Tóth, Csaba D.; Weighill, Thomas

Date: 2023-07-02

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

arXiv ID: 2307.00704 [cs]

Attachments:

• storage/ZCVB7NV8/Akitaya et al_2023_Reconfiguration of Polygonal Subdivisions via Recombination [Manuscript].pdf - View on Google Drive

Galactic Token Sliding

Type: manuscript

Authors: Bartier, Valentin; Bousquet, Nicolas; Mouawad, Amer E.

Date: 2022-04-12

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

arXiv ID: 2204.05549

Attachments:

• storage/LQ9YVCDF/Bartier_Bousquet_Mouawad_2022_Galactic Token Sliding [Manuscript].pdf - View on Google Drive

Rerouting Planar Curves and Disjoint Paths

Type: manuscript

Authors: Ito, Takehiro; Iwamasa, Yuni; Kakimura, Naonori; Kobayashi, Yusuke; Maezawa, Shun-ichi; Nozaki, Yuta; Okamoto, Yoshio; Ozeki, Kenta

Date: 2022-10-21

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

arXiv ID: 2210.11778 [cs, math]

Attachments:

• storage/7D8LDTXC/Ito et al_2022_Rerouting Planar Curves and Disjoint Paths [Manuscript].pdf - View on Google Drive

1-Complex s,t Hamiltonian Paths: Structure and Reconfiguration in Rectangular Grids

Type: manuscript

Authors: Nishat, Rahnuma Islam; Srinivasan, Venkatesh; Whitesides, Sue

Date: 2022

Attachments:

• storage/2FDB8Q5U/Nishat_Srinivasan_Whitesides_2022_1-Complex s,t Hamiltonian Paths - Structure and Reconfiguration in Rectangular Grids [Manuscript].pdf - View on Google Drive

A note on the flip distance between non-crossing spanning trees

Type: manuscript

Authors: Bousquet, Nicolas; Gledel, Valentin; Narboni, Jonathan; Pierron, Théo

Date: 2023-03-14

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

arXiv ID: 2303.07710 [cs, math]

Attachments:

• storage/TMNS5KTV/Bousquet et al_2023_A note on the flip distance between non-crossing spanning trees [Manuscript].pdf - View on Google Drive

Vizing's edge-recoloring conjecture holds

Type: manuscript

Authors: Narboni, Jonathan

Date: 2023/02/24

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

DOI: 10.48550/arXiv.2302.12914

Attachments:

• storage/ECC27VAL/Narboni_2023_Vizing's edge-recoloring conjecture holds [Manuscript].pdf - View on Google Drive

A dichotomy theorem for $\Gamma$-switchable $H$-colouring on $m$-edge coloured graphs

Type: manuscript

Authors: Brewster, Richard; Kidner, Arnott; MacGillivray, Gary

Date: 2023-06-09

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

arXiv ID: 2306.05962 [cs, math]

Attachments:

• storage/ZJEQGSIF/Brewster_Kidner_MacGillivray_2023_A dichotomy theorem for $-Gamma$-switchable $H$-colouring on $m$-edge coloured graphs [Manuscript].pdf - View on Google Drive

The Realizability of Theta Graphs as Reconfiguration Graphs of Minimum Independent Dominating Sets

Type: manuscript

Authors: Brewster, Richard; Mynhardt, Kieka; Teshima, Laura

Date: 2023-05-28

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

arXiv ID: 2305.17814 [math]

Attachments:

• storage/B4YJNSHV/Brewster_Mynhardt_Teshima_2023_The Realizability of Theta Graphs as Reconfiguration Graphs of Minimum Independent Dominating Sets [Manuscript].pdf - View on Google Drive

Random Graphs with Prescribed $K$-Core Sequences: A New Null Model for Network Analysis

Type: manuscript

Authors: Van Koevering, Katherine; Benson, Austin R.; Kleinberg, Jon

Date: 2021

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

Attachments:

• storage/6CMHDEDZ/Van Koevering_Benson_Kleinberg_2021_Random Graphs with Prescribed $K$-Core Sequences [Manuscript].pdf - View on Google Drive

On the Laplacian spectra of token graphs

Type: manuscript

Authors: Dalfó, C.; Duque, F.; Fabila-Monroy, R.; Fiol, M. A.; Huemer, C.; Trujillo-Negrete, A. L.; Martínez, F. J. Zaragoza

Date: 2020/12/01

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

arXiv ID: 2012.00808

Attachments:

• storage/7AP2YCEW/Dalfó et al_2020_On the Laplacian spectra of token graphs [Manuscript].pdf - View on Google Drive

On Reconfiguration Graph of Independent Sets under Token Sliding

Type: manuscript

Authors: Avis, David; Hoang, Duc A.

Date: 2022/03/31

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

arXiv ID: 2203.16861

Attachments:

• storage/KNL883CC/Avis_Hoang_2022_On Reconfiguration Graph of Independent Sets under Token Sliding [Manuscript].pdf - View on Google Drive

Independent set reconfiguration: general and RNA-focused parameterized algorithms

Type: manuscript

Authors: Boury, Théo; Bulteau, Laurent; Marchand, Bertrand; Ponty, Yann

Date: 2023

Attachments:

• storage/KGUQ5VAR/Boury et al_2023_Independent set reconfiguration - general and RNA-focused parameterized algorithms [Manuscript].pdf - View on Google Drive

Fixed-Parameter Algorithms for Graph Constraint Logic

Type: manuscript

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

Date: 2020-11-20

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

arXiv ID: 2011.10385

Attachments:

• storage/IA3SHYBW/Hatanaka et al_2020_Fixed-Parameter Algorithms for Graph Constraint Logic [Manuscript].pdf - View on Google Drive

Garland's method for token graphs

Type: manuscript

Authors: Lew, Alan

Date: 2023-05-03

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

arXiv ID: 2305.02406 [math]

Attachments:

• storage/KJFMMNFE/Lew_2023_Garland's method for token graphs [Manuscript].pdf - View on Google Drive

Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes

Type: manuscript

Authors: Golovach, Petr A.; Stamoulis, Giannos; Thilikos, Dimitrios M.

Date: 2022-11-03

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

arXiv ID: 2211.01723 [cs, math]

Attachments:

• storage/9SAP5PJL/Golovach_Stamoulis_Thilikos_2022_Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes [Manuscript].pdf - View on Google Drive

Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra

Type: manuscript

Authors: Ito, Takehiro; Kakimura, Naonori; Kamiyama, Naoyuki; Kobayashi, Yusuke; Maezawa, Shun-ichi; Nozaki, Yuta; Okamoto, Yoshio

Date: 2023-04-28

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

arXiv ID: 2304.14782 [cs, math]

Attachments:

• storage/HUSZQD6Z/Ito et al_2023_Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra [Manuscript].pdf - View on Google Drive

Distributed recoloring of interval and chordal graphs

Type: manuscript

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

Date: 2021/09/13

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

Attachments:

• storage/KZMCG2X6/Bousquet et al_2021_Distributed recoloring of interval and chordal graphs [Manuscript].pdf - View on Google Drive

Reconfiguration of graphs with connectivity constraints

Type: manuscript

Authors: Bousquet, Nicolas; Mary, Arnaud

Date: 2018-09-14

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

arXiv ID: 1809.05443

Attachments:

• storage/3GJR8PQN/Bousquet_Mary_2018_Reconfiguration of graphs with connectivity constraints [Manuscript].pdf - View on Google Drive

On Approximate Reconfigurability of Label Cover

Type: manuscript

Authors: Ohsaka, Naoto

Date: 2023-04-18

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

arXiv ID: 2304.08746 [cs]

Attachments:

• storage/XTHIVYIA/Ohsaka_2023_On Approximate Reconfigurability of Label Cover [Manuscript].pdf - View on Google Drive

Flip Graphs for Matrix Multiplication

Type: manuscript

Authors: Kauers, Manuel; Moosbauer, Jakob

Date: 2022-12-02

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

arXiv ID: 2212.01175 [cs]

Attachments:

• storage/TBCTN8SZ/Kauers_Moosbauer_2022_Flip Graphs for Matrix Multiplication [Manuscript].pdf - View on Google Drive

Hamilton Paths in Dominating Graphs of Trees and Cycles

Type: manuscript

Authors: Adaricheva, Kira; Blake, Heather Smith; Bozeman, Chassidy; Clarke, Nancy E.; Haas, Ruth; Messinger, Margaret-Ellen; Seyffarth, Karen

Date: 2021-12-08

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

arXiv ID: 2112.04448

Attachments:

• storage/7P7MXTWT/Adaricheva et al_2021_Hamilton Paths in Dominating Graphs of Trees and Cycles [Manuscript].pdf - View on Google Drive

Complexity of Reconfiguration in Surface Chemical Reaction Networks

Type: manuscript

Authors: Alaniz, Robert M.; Brunner, Josh; Coulombe, Michael; Demaine, Erik D.; Diomidov, Yevhenii; Knobel, Ryan; Gomez, Timothy; Grizzell, Elise; Lynch, Jayson; Rodriguez, Andrew; Schweller, Robert; Wylie, Tim

Date: 2023/03/27

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

Attachments:

• storage/Y3IDHZAC/Alaniz et al_2023_Complexity of Reconfiguration in Surface Chemical Reaction Networks [Manuscript].pdf - View on Google Drive

Recolouring planar graphs of girth at least five

Type: manuscript

Authors: Bartier, Valentin; Bousquet, Nicolas; Feghali, Carl; Heinrich, Marc; Moore, Benjamin; Pierron, Théo

Date: 2021-12-01

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

arXiv ID: 2112.00631

Attachments:

• storage/XCXS5VBX/Bartier et al_2021_Recolouring planar graphs of girth at least five [Journal Article].pdf - View on Google Drive

Reconfiguration graphs of zero forcing sets

Type: manuscript

Authors: Geneson, Jesse; Haas, Ruth; Hogben, Leslie

Date: 2020-09-01

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

arXiv ID: 2009.00220

Attachments:

• storage/CZ59WVUC/Geneson_Haas_Hogben_2020_Reconfiguration graphs of zero forcing sets [Manuscript].pdf - View on Google Drive

Token Swapping on Trees

Type: manuscript

Authors: Biniaz, Ahmad; Jain, Kshitij; Lubiw, Anna; Masárová, Zuzana; Miltzow, Tillmann; Mondal, Debajyoti; Naredla, Anurag Murty; Tkadlec, Josef; Turcotte, Alexi

Date: 2019-03-16

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

arXiv ID: 1903.06981

Attachments:

• storage/DMAJ9U7A/Biniaz et al_2019_Token Swapping on Trees [Manuscript].pdf - View on Google Drive

The $i$-Graphs of Paths and Cycles

Type: manuscript

Authors: Brewster, R. C.; Mynhardt, C. M.; Teshima, L. E.

Date: 2023-03-14

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

arXiv ID: 2303.08190 [math]

Attachments:

• storage/PYVK3XCI/Brewster_Mynhardt_Teshima_2023_The $i$-Graphs of Paths and Cycles [Manuscript].pdf - View on Google Drive

On the Automorphism Group of Token Graphs of Complete Bipartite Graphs and Cartesian Products of Connected Graphs

Type: manuscript

Authors: Fabila-Monroy, Ruy; Trujillo-Negrete, Ana Laura

Date: 2023-02-15

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

arXiv ID: 2302.07914 [math]

Attachments:

• storage/AECMT68R/Fabila-Monroy_Trujillo-Negrete_2023_On the Automorphism Group of Token Graphs of Complete Bipartite Graphs and Cartesian Products of Connected Graphs [Manuscript].pdf - View on Google Drive

Reconfiguration of Minimum Independent Dominating Sets in Graphs

Type: manuscript

Authors: Brewster, R. C.; Mynhardt, C. M.; Teshima, L. E.

Date: 2023-03-10

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

arXiv ID: 2303.06299 [math]

Attachments:

• storage/9PZLSAMP/Brewster_Mynhardt_Teshima_2023_Reconfiguration of Minimum Independent Dominating Sets in Graphs [Manuscript].pdf - View on Google Drive

Flipping Plane Spanning Paths

Type: manuscript

Authors: Aichholzer, Oswin; Knorr, Kristin; Mulzer, Wolfgang; Obenaus, Johannes; Paul, Rosna; Vogtenhuber, Birgit

Date: 2022-09-27

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

arXiv ID: 2202.10831 [cs]