| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2014-04-24 14:20 支配集合の遷移可能性 ○鈴木 顕（東北大）・Amer Mouawad・Naomi Nishimura（ウォータールー大）  COMP2014-5 |
|
| 抄録 | （和） | 本論文では支配集合の遷移可能性問題を扱う． 支配集合とは，グラフ$G$の点集合の部分集合$S$のうち， $G$の各点が$S$に含まれるか$S$と隣接しているものをいう． 支配集合の遷移可能性問題とは，あるグラフに対する2つの支配集合が与えられ， それらを繋ぐ支配集合の列が存在するか判定する問題である． ただし，列内の支配集合同士が隣接するためには，隣接条件を満たさなければならない． 本論文では，一方の支配集合に対して点を1つ加えるか取り除くことでもう一方の支配集合が得られるときに， 2つの支配集合は隣接すると定義した． ある整数$k$に対して， 点集合が高々$k$点からなるグラフ$G$の支配集合の集合であり， 隣接条件を満たす支配集合同士に辺を引いたグラフ$D_k(G)$を考える． 我々は2013年にHaasとSeyffarthによって立てられた， $D_{Gamma(G)+1}(G)$は常に連結であるという予想に対する反例を与えた． ここで$Gamma(G)$とは$G$の極小支配集合の点数の最大値である． 我々の反例は，グラフクラスを平面グラフ，木幅制限グラフ，$b$部グラフ，$b ge 3$，に制限しても成り立つ． さらに我々は，$D_{gamma(G)+1}(G)$の直径が指数長になるようなグラフの族を与えた． ここで$gamma(G)$とは$G$の最小支配集合の点数である． 一方で我々は，$n$点からなるグラフ$G$が少なくとも$m+1$本の互いに素な辺を持っていれば， $D_{n-m}(G)$は常に連結であり，その直径は$n$に対する線形長であることを示した． |
| （英） | We explore a reconfiguration version of the dominating set problem, where a dominating set in a graph $G$ is a set $S$ of vertices such that each vertex is either in $S$ or has a neighbour in $S$. In a reconfiguration problem, the goal is to determine whether there exists a sequence of feasible solutions connecting given feasible solutions $s$ and $t$ such that each pair of consecutive solutions is adjacent according to a specified adjacency relation. Two dominating sets are adjacent if one can be formed from the other by the addition or deletion of a single vertex. For various values of $k$, we consider properties of $D_k(G)$, the graph consisting of a vertex for each dominating set of size at most $k$ and edges specified by the adjacency relation. Addressing an open question posed by Haas and Seyffarth, we demonstrate that $D_{Gamma(G)+1}(G)$ is not necessarily connected, for $Gamma(G)$ the maximum cardinality of a minimal dominating set in $G$. The result holds even when graphs are constrained to be planar, of bounded tree-width, or $b$-partite for $b ge 3$. Moreover, we construct an infinite family of graphs such that $D_{gamma(G)+1}(G)$ has exponential diameter, for $gamma(G)$ the minimum size of a dominating set. On the positive side, we show that $D_{n-m}(G)$ is connected and of linear diameter for any graph $G$ on $n$ vertices having at least $m+1$ independent edges. |
|
| キーワード | （和） | 支配集合 / 遷移可能性問題 / 直径 / 連結性 / / / / |
| （英） | connectivity / diameter / dominating set / reconfiguration problem / / / / | |
| 文献情報 | 信学技報, vol. 114, no. 19, COMP2014-5, pp. 29-35, 2014年4月. | |
| 資料番号 | COMP2014-5 | |
| 発行日 | 2014-04-17 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2014-5 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2014-04-24 - 2014-04-24 |
| 開催地（和） | 東北大学 |
| 開催地（英） | Tohoku University |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2014-04-COMP |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | 支配集合の遷移可能性 |
| サブタイトル（和） | |
| タイトル（英） | Reconfiguration of Dominating Sets |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 支配集合 / connectivity |
| キーワード(2)（和/英） | 遷移可能性問題 / diameter |
| キーワード(3)（和/英） | 直径 / dominating set |
| キーワード(4)（和/英） | 連結性 / reconfiguration problem |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 鈴木 顕 / Akira Suzuki / スズキ アキラ |
| 第1著者 所属（和/英） | 東北大学 (略称： 東北大) Tohoku University (略称： Tohoku Univ.) |
| 第2著者 氏名（和/英/ヨミ） | Amer Mouawad / Amer Mouawad / |
| 第2著者 所属（和/英） | ウォータールー大学 (略称： ウォータールー大) University of Waterloo (略称： Univ. of Waterloo) |
| 第3著者 氏名（和/英/ヨミ） | Naomi Nishimura / Naomi Nishimura / |
| 第3著者 所属（和/英） | ウォータールー大学 (略称： ウォータールー大) University of Waterloo (略称： Univ. of Waterloo) |
| 講演者 | 第1著者 |
| 発表日時 | 2014-04-24 14:20:00 |
| 発表時間 | 35分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2014-5 |
| 巻番号（vol） | vol.114 |
| 号番号（no） | no.19 |
| ページ範囲 | pp.29-35 |
| ページ数 | 7 |
| 発行日 | 2014-04-17 (COMP) |
[研究会発表申込システムのトップページに戻る]