| 大会名称 |
|---|
| 2019年 総合大会 |
| 大会コ－ド |
| 2019G |
| 開催年 |
| 2019 |
| 発行日 |
| 2019-03-05 |
| セッション番号 |
| DS-1 |
| セッション名 |
| COMP 学生シンポジウム |
| 講演日 |
| 2019/03/19 |
| 講演場所(会議室等) |
| 54号館 102教室 |
| 講演番号 |
| DS-1-9 |
| タイトル |
| 単位円グラフに対するL(2,1)-ラベリングの8.5-近似アルゴリズム |
| 著者名 |
| ◎山中寿登, 小野廣隆, |
| キーワード |
| グラフラベリング, L(2,1)-ラベリング, 単位円グラフ, グラフアルゴリズム |
| 抄録 |
| 与えられたグラフの任意の頂点u, vに対して, uとvが隣接するとき|L(u)-L(v)|≧2を, uとvの距離が2のときL(u)≠L(v)を満たすような, 頂点の非負整数の割り当てLをL(2, 1)-ラベリングという. L(2, 1)-ラベリング問題は割り当てLのラベルの値の範囲(つまりmax(L(u)) - min(L(u)) + 1)を最小化するものである. これまで単位円グラフに対するFialaらによる分割統治型の12近似アルゴリズムが知られている. 本論文では, これを改善する8.5-近似アルゴリズムを提案する. 近似率12からの改善はグラフの最大次数に着目した前処理の採用と, Fiala らのアルゴリズムで用いられた分割とは異なる分割を利用することにより, 達成している. |
| 本文pdf |
|
PDF download
|