グラフの最小出次数最大化問題

• Item type: SIG Technical Reports(1)
• 公開日: 2009-05-04
• タイトル: グラフの最小出次数最大化問題
• タイトル / 言語: en
• タイトル: On Graph Orientation to Maximize the Minimum Weighted Outdegree
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 九州産業大学情報科学部情報科学科
• 著者所属: お茶の水大学
• 著者所属: 九州工業大学大学院情報工学研究院システム創成情報工学系
• 著者所属: 九州大学大学院システム情報科学研究院情報学部門
• 著者所属(英): en
• 著者所属(英): Department of Information Science, Kyushu Sangyo University
• 著者所属(英): en
• 著者所属(英): Ochanomizu University
• 著者所属(英): en
• 著者所属(英): Department of Systems Design and Informatics, Kyushu Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Informatics, Kyushu University
• 著者名: 朝廣, 雄一; Jesper, Jansson; 宮野, 英次; 小野, 廣隆
• 著者名(英): Yuichi, Asahiro; Jesper, Jansson; Eiji, Miyano; Hirotaka, Ono
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: MAXMINO という無向グラフの向き付け問題の一種について考える．無向枝重みつきグラフの向き付けを与えることにより，重み付き出次数を定義する （枝重みは正整数であるとする）．この問題は，グラフ中の最小重み付き出次数を最大化する問題である．本研究ではまず，MAXMINO は枝重みを {1 , 2} に限定し，かつ各頂点の （重みなし） 次数が高々 3，さらにグラフが平面二部であるような場合でも強 NP 困難であり，P= NP でない限り，任意の定数 E ＞ 0 に対して多項式時間では 2 - E 近似不可能であることを示す．次にすべての枝重みが 1 である場合には，多項式時間で解くことができることを示す．これにより，枝重みが wmin よりも大きい枝数が O (log n)であるときにも，多項式時間で解くことができる．さらに，この手法により MAXMINO に対する単純な wmax / wmin 近似多項式時間アルゴリズムを得ることができる （wmax，wmin はそれぞれ枝重みの最大値，最小値)．最後に，入力グラフがカクタスである場合にも MAXMINO は多項式時間で解くことができることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We study a new variant of the graph orientation problem called MAXMINO where the input is an undirected, edge-weighted graph and the objective is to assign a direction to each edge so that the minimum weighted outdegree (taken over all vertices in the resulting directed graph) is maximized. All edge weights are assumed to be positive integers. First, we prove that MAXMINO is strongly NP-hard and cannot be approximated within a ratio of 2 - E for any constant E > 0 in polynomial time unless P=NP, even if all edge weights belong to {1, 2}, every vertex has degree at most three, and the input graph is bipartite or planar. Next, we show how to solve MAXMINO exactly in polynomial time for the special case in which all edge weights are equal to 1. This technique gives us a simple polynomial-time wmax / wmin -approximation algorithm for MAXMINO where wmax and wmin denote the maximum and minimum weights among all the input edges. Furthermore, we also observe that this approach yields an exact algorithm for the general case of MAXMINO whose running time is polynomial whenever the number of edges having weight larger than wmin is at most logarithmic in the number of vertices. Finally, we show that MAXMINO is solvable in polynomial time if the input is a cactus graph.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2009-AL-124, 号 7, p. 1-8, 発行日 2009-05-04
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会