講演抄録/キーワード |
講演名 |
2013-12-20 09:55
グラフの独立点集合遷移問題に対するアルゴリズム エリック ドメイン・マーチン ドメイン(マサチューセッツ工科大)・伊藤健洋(東北大)・小野廣隆(九大)・○上原隆平(北陸先端大) COMP2013-39 |
抄録 |
(和) |
グラフG に対し,|Ibj| = |Ir| であるような2 つの独立点集合Ib とIr が与えられたとする.また,G において,Ib に含まれる各点にはトークンが置かれているとする.スライディングトークン問題とは,Ib からIr へのGの独立点集合の系列が存在するか判定する問題である.ただし,系列に含まれる各独立点集合は,その1 つ前の独立点集合から,ただ1 つのトークンをG の辺に沿ってスライドさせることで得られなければならない.この問題は,理想グラフに対してPSPACE 完全であることが知られている.本論文では,理想グラフのいくつかの部分クラスに対して,この問題がO(n) 時間で解けることを示す.ここで,n はグラフの点数である.また,これらのグラフに対しては,実際にIb からIr へ遷移させる最短の系列を多項式時間で見つけることができる. |
(英) |
Suppose that we are given two independent sets Ib and Ir of a graph such that |Ibj| = |Ir|, and imagine that a token is placed on each vertex in Ib. Then, sliding token is to determine whether there exists a sequence of independent sets which transforms Ib into Ir so that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph. This problem is known to be PSPACE-complete for perfect graphs. In this paper, we show that the problem is solvable in O(n) time for proper interval graphs and trivially perfect graphs, both of which are subclasses of the class of perfect graphs, where n is the number of vertices in a graph. For these graph classes, we can nd an actual sequence of independent sets between Ib and Ir with the minimum number of token-slidings, in polynomial time. |
キーワード |
(和) |
グラフアルゴリズム / スライディングトークン / 遷移問題 / 独立点集合 / / / / |
(英) |
graph algorithm / independent set / reconfiguration problem / sliding token / / / / |
文献情報 |
信学技報, vol. 113, no. 371, COMP2013-39, pp. 7-14, 2013年12月. |
資料番号 |
COMP2013-39 |
発行日 |
2013-12-13 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2013-39 |