Reconfiguring Hamiltonian Cycles in L-Shaped Grid Graphs

被引：13
|
作者：
Nishat, Rahnuma Islam [1 ]
Whitesides, Sue [1 ]
机构：
[1] Univ Victoria, Dept Comp Sci, Victoria, BC, Canada
来源：
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE (WG 2019) | 2019年 / 11789卷
基金：
加拿大自然科学与工程研究理事会;
关键词：
Hamilton cycle; Reconfiguration; Grid graph; Algorithm; ENUMERATION; COSTS;
D O I：
10.1007/978-3-030-30786-8_25
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Given a pair of 1-complex Hamiltonian cycles C and C' in an L-shaped grid graph G, we show that one is reachable from the other under two operations, flip and transpose, while remaining in the family of 1-complex Hamiltonian cycles throughout the reconfiguration. Operations flip and transpose are local in G. We give a reconfiguration algorithm that uses O(vertical bar G vertical bar) operations.
引用
收藏
页码：325 / 337
页数：13
相关论文
共 50 条
  • [1] Hamiltonian paths in L-shaped grid graphs
    Keshavarz-Kohjerdi, Fatemeh
    Bagheri, Alireza
    THEORETICAL COMPUTER SCIENCE, 2016, 621 : 37 - 56
  • [2] Longest (s, t)-paths in L-shaped grid graphs
    Keshavarz-Kohjerdi, Fatemeh
    Bagheri, Alireza
    OPTIMIZATION METHODS & SOFTWARE, 2019, 34 (04): : 797 - 826
  • [3] A bandwidth reduction algorithm for L-shaped and Z-shaped grid structured graphs
    Doss, L. Jones Tarcius
    Arathi, P.
    OPERATIONS RESEARCH LETTERS, 2011, 39 (06) : 441 - 446
  • [4] Hamiltonian cycles in solid grid graphs
    Umans, C
    Lenhart, W
    38TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1997, : 496 - 505
  • [5] The hamiltonicity, hamiltonian connectivity, and longest (s, t)-path of L-shaped supergrid graphs
    Keshavarz-Kohjerdi, Fatemeh
    Hung, Ruo-Wei
    IAENG International Journal of Computer Science, 2020, 47 (03): : 378 - 391
  • [6] Reconfiguration of Hamiltonian Cycles in Rectangular Grid Graphs
    Nishat, Rahnuma Islam
    Whitesides, Sue
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2023, 34 (07) : 773 - 793
  • [7] Bend Complexity and Hamiltonian Cycles in Grid Graphs
    Nishat, Rahnuma Islam
    Whitesides, Sue
    COMPUTING AND COMBINATORICS, COCOON 2017, 2017, 10392 : 445 - 456
  • [8] Enumeration of Hamiltonian Cycles in Some Grid Graphs
    Bodroza-Pantic, Olga
    Pantic, Bojana
    Pantic, Ilija
    Bodroza-Solarov, Marija
    MATCH-COMMUNICATIONS IN MATHEMATICAL AND IN COMPUTER CHEMISTRY, 2013, 70 (01) : 181 - 204
  • [9] Reconfiguring Simple s, t Hamiltonian Paths in Rectangular Grid Graphs
    Nishat, Rahnuma Islam
    Srinivasan, Venkatesh
    Whitesides, Sue
    COMBINATORIAL ALGORITHMS, IWOCA 2021, 2021, 12757 : 501 - 515
  • [10] Edge intersection graphs of L-shaped paths in grids
    Cameron, Kathie
    Chaplick, Steven
    Hoang, Chinh T.
    DISCRETE APPLIED MATHEMATICS, 2016, 210 : 185 - 194
12345