講演抄録/キーワード |
講演名 |
2015-04-23 13:10
支配集合遷移問題に対するアルゴリズム Arash Haddadan(ウォータールー大)・伊藤健洋(東北大)・Amer E. Mouawad・Naomi Nishimura(ウォータールー大)・小野廣隆(九大)・○鈴木 顕(東北大)・Youcef Tebbal(ウォータールー大) COMP2015-1 |
抄録 |
(和) |
支配集合遷移問題とは,グラフ$G$の2つの支配集合$D_s$と$D_t$,
しきい値$k$が与えられた際に,
点の追加と削除の操作を繰り返して$D_s$から$D_t$へ遷移することが可能か判定する問題である.
その際,1点の追加または削除で得られる各集合もまた,
サイズがしきい値$k$以下の$G$の支配集合でなければならない.
支配集合遷移問題は一般のグラフに対してPSPACE完全と知られている.
本研究では,入力グラフをコグラフ,木,または区間グラフに限定した際に,
この問題を線形時間で解くアルゴリズムを与えた. |
(英) |
Suppose that we are given two dominating sets $D_s$ and $D_t$ of a graph $G$
whose cardinalities are at most a given threshold $k$.
Then, we are asked whether there exists a sequence of dominating sets of $G$ between
$D_s$ and $D_t$ such that each dominating set in the sequence is of cardinality
at most $k$ and can be obtained from the previous one by either adding or deleting exactly one vertex.
This problem is known to be PSPACE-complete in general.
In this paper, we give a general scheme to construct linear-time algorithms, and show
that the problem can be solved in linear time for cographs, trees, and interval graphs. |
キーワード |
(和) |
木 / 区間グラフ / コグラフ / 支配集合 / 遷移問題 / / / |
(英) |
cograph / combinatorial reconfiguration / dominating set / interval graph / tree / / / |
文献情報 |
信学技報, vol. 115, no. 15, COMP2015-1, pp. 1-7, 2015年4月. |
資料番号 |
COMP2015-1 |
発行日 |
2015-04-16 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2015-1 |