多重リスト彩色問題の計算複雑性と近似保証付きアルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 2019-02-26
• タイトル: 多重リスト彩色問題の計算複雑性と近似保証付きアルゴリズム
• タイトル / 言語: en
• タイトル: Computational complexity and an algorithm with approximate guarantee for the list multi-coloring probleme
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 電気通信大学
• 著者所属(英): en
• 著者所属(英): The University of Electro-Communications
• 著者名: 蛭田, 海斗
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 多重リスト彩色問題とは，グラフと，グラフの頂点ごとに塗ることが許された色のリストが与えられ，そのリストの中から，辺で結ばれた頂点間には同じ色が割り当てられないように，複数個の色を選ぶ問題である．このとき，それぞれの頂点に割り当てられる色の数が，なるべく平等になることが望まれる．多重リスト彩色問題は，優先ユーザを考慮した周波数割り当てのモデル化で用いられ，いくつかのヒューリスティックなアルゴリズムが提案されているが，出力が保証されているものは殆ど無い．本研究では，最も割り当てられた色の個数が少ない頂点の色の数を最大化する問題について取り扱う．そのような多重リスト彩色問題を最小値最大化多重リスト彩色問題と呼び，その計算複雜性を明らかにすること，および，近似保証付きアルゴリズムの設計を研究目的とする．それらの目的について，本研究では，いくつかのグラフ族における計算複雜性，一般グラフでの近似不可能性，および，特殊なクリーク分割が存在するグラフでは近似保証がある多項式時間アルゴリズムが得られることを示した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In the list multi-coloring problem, we are given a graph and lists of colors for its vertices, and we select colors for each vertex from the list so that the same color is not assigned between adjacent vertices. Moreover, it is desirable that the number of colors assigned to each vertex is as equal as possible. The list multi-coloring problem models frequency allocation under the existence of priority users. Although several heuristic algorithms have been proposed, they merely have outputs with any guarantees. In this research, we deal with the problem of maximizing the smallest number of colors assigned to a vertex. The goal of this research is to reveal the computation complexity of that problem and to solve that problem with guarantee. To this end, we show that the computational complexity for some graph classes, the inapproximability for general graphs, and a polynomial-time algorithm with approximate guarantee for graphs which can be divided into cliques with a special property.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2019-AL-172, 号 5, p. 1-8, 発行日 2019-02-26
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会