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

講演抄録/キーワード
講演名 2012-12-10 15:50
グラフのリストL(2,1)ラベリングの遷移可能性
伊藤健洋・○川村一斗東北大)・小野廣隆九大)・周 暁東北大
技報オンラインサービス実施中
抄録 (和) 非負整数$k \ge 0$に対し,グラフ$G$の各点$v$には,ラベルの集合$C(v) \subseteq \{0,1, \ldots, k\}$が与えられているとする.
このとき,$G$のリスト$L(2,1)$ラベリングとは,$G$の各点$v$に$C(v)$に含まれるラベルを1つ割り当てることをいう.
ただし,隣接する任意の2点には少なくとも$2$離れたラベルを割り当て,距離2にある任意の2点には少なくとも$1$離れたラベルを割り当てなければならない.
本論文では,グラフ$G$のリスト$L(2,1)$ラベリングが2つ与えられたとき,一方のラベル割当から他方のラベル割当へ段階的に遷移させたい.
ただし,1回に変更できるのは1点のラベル割当のみであり,こうして得られるラベル割当もやはり$G$のリスト$L(2,1)$ラベリングでなければならない.
本論文では,$k \ge 6$のとき,この問題は平面二部グラフに対してPSPACE完全であることを証明する.
一方で,$k \le 4$のときには,この問題が任意のグラフに対して線形時間で解けることを示す.
さらに,グラフを木に限定したとき,任意の2つのリスト$L(2,1)$ラベリングが互いに遷移できるための十分条件を与える. 
(英) For an integer $k \ge 0$, suppose that each vertex $v$ of a graph $G$ has a set $C(v) \subseteq \{0,1, \ldots, k\}$ of labels, called a list of $v$. A list $L(2,1)$-labeling of $G$ is an assignment of a label in $C(v)$ to each vertex $v$ of $G$ such that every two adjacent vertices receive labels which differ by at least $2$ and every two vertices of distance two receive labels which differ by at least $1$. In this paper, we study the problem of reconfiguring one list $L(2,1)$-labeling of a graph into another list $L(2,1)$-labeling of the same graph by changing only one label assignment at a time, while at all times maintaining a list $L(2,1)$-labeling. First we show that this decision problem is PSPACE-complete, even for bipartite planar graphs and $k \geq 6$. In contrast, we then show that the problem can be solved in linear time for general graphs if $k \leq 4$. We finally consider the problem restricted to trees, and give a sufficient condition for which any two list $L(2,1)$-labelings of a tree can be transformed into each other.
キーワード (和) グラフアルゴリズム / L(2,1)ラベリング / 遷移問題 / / / / /  
(英) graph algorithm / L(2,1)-labeling / reconfiguration problem / / / / /  
文献情報 信学技報, vol. 112, no. 340, COMP2012-49, pp. 33-40, 2012年12月.
資料番号 COMP2012-49 
発行日 2012-12-03 (COMP) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380

研究会情報
研究会 COMP  
開催期間 2012-12-10 - 2012-12-10 
開催地(和) 九州大学 
開催地(英) Kyushu University 
テーマ(和)  
テーマ(英)  
講演論文情報の詳細
申込み研究会 COMP 
会議コード 2012-12-COMP 
本文の言語 英語(日本語タイトルあり) 
タイトル(和) グラフのリストL(2,1)ラベリングの遷移可能性 
サブタイトル(和)  
タイトル(英) Reconfiguration of List L(2,1)-Labelings in a Graph 
サブタイトル(英)  
キーワード(1)(和/英) グラフアルゴリズム / graph algorithm  
キーワード(2)(和/英) L(2,1)ラベリング / L(2,1)-labeling  
キーワード(3)(和/英) 遷移問題 / reconfiguration problem  
キーワード(4)(和/英) /  
キーワード(5)(和/英) /  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 伊藤 健洋 / Takehiro Ito / イトウタ ケヒロ
第1著者 所属(和/英) 東北大学 (略称: 東北大)
Tohoku University (略称: Tohoku Univ.)
第2著者 氏名(和/英/ヨミ) 川村 一斗 / Kazuto Kawamura / カワムラ カズト
第2著者 所属(和/英) 東北大学 (略称: 東北大)
Tohoku University (略称: Tohoku Univ.)
第3著者 氏名(和/英/ヨミ) 小野 廣隆 / Hirotaka Ono / オノ ヒロタカ
第3著者 所属(和/英) 九州大学 (略称: 九大)
Kyushu University (略称: Kyushu Univ.)
第4著者 氏名(和/英/ヨミ) 周 暁 / Xiao Zhou / シュウ ギョウ
第4著者 所属(和/英) 東北大学 (略称: 東北大)
Tohoku University (略称: Tohoku Univ.)
第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著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2012-12-10 15:50:00 
発表時間 35 
申込先研究会 COMP 
資料番号 IEICE-COMP2012-49 
巻番号(vol) IEICE-112 
号番号(no) no.340 
ページ範囲 pp.33-40 
ページ数 IEICE-8 
発行日 IEICE-COMP-2012-12-03 


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

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


IEICE / 電子情報通信学会