WEKO3
アイテム
三角格子点上の単位円グラフに対する多重彩色
https://ipsj.ixsq.nii.ac.jp/records/31829
https://ipsj.ixsq.nii.ac.jp/records/31829a4d7b98e-ec17-4d5a-8892-748edd437f90
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
Copyright (c) 2004 by the Information Processing Society of Japan
|
|
オープンアクセス |
Item type | SIG Technical Reports(1) | |||||||
---|---|---|---|---|---|---|---|---|
公開日 | 2004-10-14 | |||||||
タイトル | ||||||||
タイトル | 三角格子点上の単位円グラフに対する多重彩色 | |||||||
タイトル | ||||||||
言語 | en | |||||||
タイトル | Multicoloring Unit Disk Graphs on Triangular Lattice Points | |||||||
言語 | ||||||||
言語 | eng | |||||||
資源タイプ | ||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
資源タイプ | technical report | |||||||
著者所属 | ||||||||
上智大学理工学部 | ||||||||
著者所属 | ||||||||
東京大学大学院理工学系研究科 | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Faculty of Science and Technology, Sophia University | ||||||||
著者所属(英) | ||||||||
en | ||||||||
Graduate School of Information Science and Technology, University of Tokyo | ||||||||
著者名 |
宮本, 裕一郎
× 宮本, 裕一郎
|
|||||||
著者名(英) |
Yuichiro, Miyamoto
× Yuichiro, Miyamoto
|
|||||||
論文抄録 | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | 与えられた非負整数mとnに対して,P(m n)def.={(xe_1+ye_2)lx∈{0 1 ... m?1} y∈{0 1 ... n-1}}と定義する.ここでe_1def.=(1 0) e_2def.=(1/2 √3/2)である,つまりP(m n)は2次元平面上の三角格子点の部分集合を表す.P(m n)を頂点集合とし,頂点間のユークリッド距離がd以下であるときに隣接と定義する無向グラフをT_m n(d)とする.本稿ではT_m n(d)がパーフェクトであるための必要条件と十分条件を議論する.具体的には,∀m∈Z_+に対してT_m n(d)がパーフェクトである必要十分条件はd≧√n^2-√3n+√3であることを示す.非負整数頂点重みw∈Z^p(m n) _+が与えられたとき,それぞれの頂点υ∈P(m n)にω(υ)色が割り当てられ,隣接するどの頂点対も同じ色を共有しないようなP(m n)への色の割り当てを(T_m n(d) ω)の多重彩色という.本稿ではP(m n)がパーフェクトであるときに(T_m n(d) ω)を多重彩色する効率的な算法も示す.本稿の主な成果であるP(m n)のパーフェクト性を利用すると一般の(T_m n(d) ω)の多重彩色に対する多項式時間精度保証付き近似解法を構成できる.こうして構成した算法は高々α(d)ω+ο(d^3)色を用いた多重彩色の解を算出する.ここでωは重み付きクリーク数である.d=1 √3 2 √7 3のとき,対応する近似率α(d)はそれぞれ(4/3) (5/3) (5/3) (7/4) (7/4)である.d>1のときα(d)≦(1+2/√3+2√3-3/d)である.また本稿では,(T_m n(d) ω)を(4/3)ω色で多重彩色できるか否か判定する問題はNP-完全であることを示す. | |||||||
論文抄録(英) | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | Given a pair of non-negative integers m and n, P(m,n) denotes a subset of 2-dimensional triangular lattice points defined by P(m,n) def.={(xe_1+ye_2)lx∈{0,1,...,m竏驤1,y∈{0,1,...,n-1}}where e_1 def.=(1,0),e2 def.=(1/2,√3/2). Let T_m,n(d) be an undirected graph defined on vertex set P(m,n) satisfying that two vertices are adjacent if and only if the Euclidean distance between the pair is less than or equal to d. In this paper, we discuss a necessary and sufficient condition that T_m,n(d) is perfect. More precisely, we show that [∀m∈Z_+, Tm,n(d) is perfect ] if and only if d≧√n^2-√3n+√3. Given a non-negative vertex weight vector w∈Z^p(m,n) _+, a multicoloring of (Tm,n(d),ω) is an assignment of colors to P(m, n) such that each vertex υ∈P(m,n) admits ω(υ) colors and every adjacent pair of two vertices does not share a common color. We also give an efficient algorithm for muliticoloring (Tm,n(d),ω) when P(m,n) is perfect. In general case, our results on the perfectness of P(m,n) implies a polynomial time approximation algorithm for multicoloring (Tm,n(d),ω). Our algorithm finds a multicoloring which uses at most α(d)ω+ο(d^3) colors, where ω denotes the weighted clique number. When d=1,√3,2√7,3, the approximation ratio α(d)=(4/3),(5/3),(5/3),(7/4),(7/4), respectively. When d>1, we showed that α(d)≦(1+2/√3+2√3-3/d). We also showed the NP-completeness of the problem to determine the existence of a multicoloring of (Tm,n(d),ω) with strictly less than (4/3)ω colors. | |||||||
書誌レコードID | ||||||||
収録物識別子タイプ | NCID | |||||||
収録物識別子 | AN1009593X | |||||||
書誌情報 |
情報処理学会研究報告アルゴリズム(AL) 巻 2004, 号 101(2004-AL-097), p. 49-54, 発行日 2004-10-14 |
|||||||
Notice | ||||||||
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
出版者 | ||||||||
言語 | ja | |||||||
出版者 | 情報処理学会 |