電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
技報オンライン
‥‥ (ESS/通ソ/エレソ/ISS)
技報アーカイブ
‥‥ (エレソ/通ソ)
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2014-04-24 14:20
支配集合の遷移可能性
鈴木 顕東北大)・Amer MouawadNaomi Nishimuraウォータールー大
技報オンラインサービス実施中
抄録 (和) 本論文では支配集合の遷移可能性問題を扱う.
支配集合とは,グラフ$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

研究会情報
研究会 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)
第4著者 氏名(和/英/ヨミ) / /
第4著者 所属(和/英) (略称: )
(略称: )
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2014-04-24 14:20:00 
発表時間 35 
申込先研究会 COMP 
資料番号 IEICE-COMP2014-5 
巻番号(vol) IEICE-114 
号番号(no) no.19 
ページ範囲 pp.29-35 
ページ数 IEICE-7 
発行日 IEICE-COMP-2014-04-17 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会