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 条

[21] Bandwidth of bipartite permutation graphs in polynomial time
Heggernes, Pinar
Kratsch, Dieter
Meister, Daniel
LATIN 2008: THEORETICAL INFORMATICS, 2008, 4957 : 216 - +
[22] Tenacity and Rupture Degree of Permutation Graphs of Complete Bipartite Graphs
Li, Fengwei
Ye, Qingfang
Li, Xueliang
BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2011, 34 (03) : 423 - 434
[23] EFFICIENT PARALLEL ALGORITHMS FOR BIPARTITE PERMUTATION GRAPHS
CHEN, L
YESHA, Y
NETWORKS, 1993, 23 (01) : 29 - 39
[24] Isomorphism classes of bipartite cycle permutation graphs
Kwak, JH
Lee, J
ARS COMBINATORIA, 1998, 50 : 139 - 148
[25] Parikh word representability of bipartite permutation graphs
Teh, Wen Chean
Ng, Zhen Chuan
Javaid, Muhammad
Chern, Zi Jing
DISCRETE APPLIED MATHEMATICS, 2020, 282 : 208 - 221
[26] Bandwidth of bipartite permutation graphs in polynomial time
Heggernes, Pinar
Kratsch, Dieter
Meister, Daniel
JOURNAL OF DISCRETE ALGORITHMS, 2009, 7 (04) : 533 - 544
[27] Random generation and enumeration of bipartite permutation graphs
Saitoh, Toshiki
Otachi, Yota
Yamanaka, Katsuhisa
Uehara, Ryuhei
JOURNAL OF DISCRETE ALGORITHMS, 2012, 10 : 84 - 97
[28] OPTIMAL PATH COVER PROBLEM ON BLOCK GRAPHS AND BIPARTITE PERMUTATION GRAPHS
SRIKANT, R
SUNDARAM, R
SINGH, KS
RANGAN, CP
THEORETICAL COMPUTER SCIENCE, 1993, 115 (02) : 351 - 357
[29] Computing the Cutwidth of Bipartite Permutation Graphs in Linear Time
Heggernes, Pinar
van 't Hof, Pim
Lokshtanov, Daniel
Nederlof, Jesper
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 2010, 6410 : 75 - +
[30] Labeling bipartite permutation graphs with a condition at distance two
Araki, Toru
DISCRETE APPLIED MATHEMATICS, 2009, 157 (08) : 1677 - 1686

← 1 2 3 4 5 →