Sliding Token on Bipartite Permutation Graphs

被引：24
|
作者：
Fox-Epstein, Eli [1 ]
Hoang, Duc A. [2 ]
Otachi, Yota [2 ]
Uehara, Ryuhei [2 ]
机构：
[1] Brown Univ, Providence, RI 02912 USA
[2] JAIST, Nomi, Japan
来源：
ALGORITHMS AND COMPUTATION, ISAAC 2015 | 2015年 / 9472卷
基金：
美国国家科学基金会;
关键词：
D O I：
10.1007/978-3-662-48971-0_21
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Sliding Token is a natural reconfiguration problem in which vertices of independent sets are iteratively replaced by neighbors. We develop techniques that may be useful in answering the conjecture that Sliding Token is polynomial-time decidable on bipartite graphs. Along the way, we give efficient algorithms for Sliding Token on bipartite permutation and bipartite distance-hereditary graphs.
引用
收藏
页码：237 / 247
页数：11
相关论文
共 50 条
  • [31] Canonical Antichains of Unit Interval and Bipartite Permutation Graphs
    Lozin, Vadim V.
    Mayhill, Colin
    ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2011, 28 (03): : 513 - 522
  • [32] Provably fastest parallel algorithms for bipartite permutation graphs
    FRL, P. O. Box 18345, Los Angeles, CA 90018, United States
    Parallel Processing Letters, 1999, 9 (03): : 385 - 390
  • [33] COMPUTING THE CUTWIDTH OF BIPARTITE PERMUTATION GRAPHS IN LINEAR TIME
    Heggernes, Pinar
    Van 't Hof, Pim
    Lokshtanov, Daniel
    Nederlof, Jesper
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2012, 26 (03) : 1008 - 1021
  • [34] Provably fastest parallel algorithms for bipartite permutation graphs
    Chen, L
    Jiang, JY
    Nyeu, MT
    INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED PROCESSING TECHNIQUES AND APPLICATIONS, VOLS I-IV, PROCEEDINGS, 1998, : 1774 - 1777
  • [35] Canonical Antichains of Unit Interval and Bipartite Permutation Graphs
    Vadim V. Lozin
    Colin Mayhill
    Order, 2011, 28 : 513 - 522
  • [36] Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs
    Heggernes, Pinar
    Meister, Daniel
    Proskurowski, Andrzej
    THEORETICAL COMPUTER SCIENCE, 2011, 412 (12-14) : 1275 - 1297
  • [37] On Reconfiguration Graphs of Independent Sets Under Token Sliding
    David Avis
    Duc A. Hoang
    Graphs and Combinatorics, 2023, 39
  • [38] On Reconfiguration Graphs of Independent Sets Under Token Sliding
    Avis, David
    Hoang, Duc A.
    GRAPHS AND COMBINATORICS, 2023, 39 (03)
  • [39] Vertex-Edge Domination in Interval and Bipartite Permutation Graphs
    Paul, Subhabrata
    Pradhan, Dinabandhu
    Verma, Shaily
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2023, 43 (04) : 947 - 963
  • [40] Bipartite permutation graphs with application to the minimum buffer size problem
    Lai, TH
    Wei, SS
    DISCRETE APPLIED MATHEMATICS, 1997, 74 (01) : 33 - 55
12345