| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2008-05-13 15:55 木のL(2,1)ラベリングに対するO(n^{1.75})時間アルゴリズム 蓮沼 徹（徳島大）・石井利昌（小樽商科大）・○小野廣隆（九大）・宇野裕之（阪府大）  COMP2008-14 |
|
| 抄録 | （和） | グラフの$L(2,1)$-ラベリングとは，頂点集合$V(G)$から非負整数への割当て$f$ で，$V(G)$上のすべての隣接する$x$と$y$に対し，$|f(x)-f(y)|\ge 2$を満たし， すべての距離$2$ で離れる$x$と$y$に対し，$|f(x)-f(y)|\ge 1$ を満たすもののことを言う．$k$-$L(2,1)$-ラベリングとは， $f:V(G)\rightarrow\{0,\ldots ,k\}$なる割当て$f$であり, $L(2,1)$-ラベリング問題とは，そのような最小の$k$を求める問題のことを言い， その最小値を$\lambda(G)$で表す． この問題はグラフの木幅が$2$のときでもNP困難であることが知られている． 木はこの問題に対して多項式時間で求解可能な数少ないグラフクラスであるが， その計算量は小さくなく， 最大次数$\Delta$，頂点数$n$の木$T$に対し，これまで$\mbox{O}(\Delta^{4.5} n)$ 時間アルゴリズムしか知られていなかった．本論文では， まず$\lambda(T)=\Delta+1$成立の既存の必要条件が$\Delta=\Omega(\sqrt{n})$ である木においては必要条件でもあることを示す．これにより $\Delta=\Omega(\sqrt{n})$の場合に$L(2,1)$-ラベリングを求める線形時間ア ルゴリズムが得られる．次に$\lambda(T)$が任意の木に対して $\mbox{O}(\Delta^{1.5}n)$時間で計算できることを示す． これらを組み合わせることにより，これまで知られていた最善の計算時間 $\mbox{O}(\Delta^{4.5} n)$を大幅に改善する $\mO(n^{1.75})$時間アルゴリズムを提案する． |
| （英） | An $L(2,1)$-labeling of a graph $G$ is an assignment $f$ from the vertex set $V(G)$ to the set of nonnegative integers such that $|f(x)-f(y)|\ge 2$ if $x$ and $y$ are adjacent and $|f(x)-f(y)|\ge 1$ if $x$ and $y$ are at distance 2 for all $x$ and $y$ in $V(G)$. A $k$-$L(2,1)$-labeling is an assignment $f:V(G)\rightarrow\{0,\ldots ,k\}$, and the $L(2,1)$-labeling problem asks the minimum $k$, which we denote by $\lambda(G)$, among all possible assignments. It is known that this problem is NP-hard even for graphs of treewidth 2. Tree is one of a few classes for which the problem is polynomially solvable, but still only an $\mbox{O}(\Delta^{4.5} n)$ time algorithm for a tree $T$ has been known so far, where $\Delta$ is the maximum degree of $T$ and $n=|V(T)|$. In this paper, we first show that an existent necessary condition for $\lambda(T)=\Delta+1$ is also sufficient for a tree $T$ with $\Delta=\Omega(\sqrt{n})$, which leads a linear time algorithm for computing $\lambda(T)$ under this condition. We then show that $\lambda(T)$ can be computed in $\mbox{O}(\Delta^{1.5}n)$ time for any tree $T$. Combining these, we finally obtain an $\mO(n^{1.75})$ time algorithm, which greatly improves the currently best known result. |
|
| キーワード | （和） | 周波数・チャンネル割当て / グラフアルゴリズム / $L(2,1)$-ラベリング / 点彩色 / / / / |
| （英） | frequency/channel assignment / graph algorithm / $L(2,1)$-labeling / vertex coloring / / / / | |
| 文献情報 | 信学技報, vol. 108, no. 29, COMP2008-14, pp. 43-50, 2008年5月. | |
| 資料番号 | COMP2008-14 | |
| 発行日 | 2008-05-06 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2008-14 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2008-05-13 - 2008-05-13 |
| 開催地（和） | 九州産業大学 |
| 開催地（英） | Kyushu Sangyo University |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2008-05-COMP |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | 木のL(2,1)ラベリングに対するO(n^{1.75})時間アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | An O(n^{1.75})-time Algorithm for L(2,1)-labeling of Trees |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 周波数・チャンネル割当て / frequency/channel assignment |
| キーワード(2)（和/英） | グラフアルゴリズム / graph algorithm |
| キーワード(3)（和/英） | $L(2,1)$-ラベリング / $L(2,1)$-labeling |
| キーワード(4)（和/英） | 点彩色 / vertex coloring |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 蓮沼 徹 / Toru Hasunuma / ハスヌマ トオル |
| 第1著者 所属（和/英） | 徳島大学 (略称： 徳島大) The University of Tokushima (略称： Univ. Tokushima) |
| 第2著者 氏名（和/英/ヨミ） | 石井 利昌 / Toshimasa Ishii / イシイ トシマサ |
| 第2著者 所属（和/英） | 小樽商科大学 (略称： 小樽商科大) Otaru University of Commerce (略称： Otaru Univ. of Commerce) |
| 第3著者 氏名（和/英/ヨミ） | 小野 廣隆 / Hirotaka Ono / オノ ヒロタカ |
| 第3著者 所属（和/英） | 九州大学 (略称： 九大) Kyushu University (略称： Kyushu Univ.) |
| 第4著者 氏名（和/英/ヨミ） | 宇野 裕之 / Yushi Uno / ウノ ユウシ |
| 第4著者 所属（和/英） | 大阪府立大学 (略称： 阪府大) Osaka Prefecture University (略称： Osaka Prefecture 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著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第3著者 |
| 発表日時 | 2008-05-13 15:55:00 |
| 発表時間 | 35分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2008-14 |
| 巻番号（vol） | vol.108 |
| 号番号（no） | no.29 |
| ページ範囲 | pp.43-50 |
| ページ数 | 8 |
| 発行日 | 2008-05-06 (COMP) |
[研究会発表申込システムのトップページに戻る]