講演抄録/キーワード |
講演名 |
2013-12-21 16:05
次数制約のあるグラフ有向化問題の近似について ○朝廣雄一(九州産大)・ジェスパー ジャンソン(京大)・宮野英次(九工大)・小野廣隆(九大) COMP2013-58 |
抄録 |
(和) |
無向グラフに対するオリエンテーション(グラフ有向化)とは,グラフ中の各辺に対して向き付けを行う
ことである.結果として得られる有向グラフにおいて,各頂点の出次数が事前に指定された下界あるいは上界を満
たす場合に,そのオリエンテーションを次数制約オリエンテーションと呼ぶ.そのようなオリエンテーションに対し
て多くの研究がなされており,色々な特徴づけが知られている.本稿では,[3] において研究された,2 つのお互いに
関連する次の最適化問題について考える.任意の固定された非負整数W に対して,Max W-Light(またはMin
W-Heavy)問題は,入力された無向グラフG のオリエンテーションのうち,出次数W 以下(またはW 以上)の頂
点数を最大化(または最小化)するものを発見することを目的とする.これらの問題の計算複雑さはW の値によっ
て変化する.本稿では,これらの問題の多項式時間での近似可能性に関するいくつかの結果を示す. |
(英) |
A degree-constrained graph orientation of an undirected graph is an assignment of a direction to each
edge in the graph such that the outdegree of every vertex in the resulting directed graph satisfies a prescribed lower
and/or upper bound. Such graph orientations have been studied in many literatures and various characterizations
are known. We consider two related optimization problems introduced in [3]: For any fixed non-negative integer W,
the problem Max W-Light (or Min W-Heavy) takes as input an undirected graph G and ask for an orientation of
G that maximizes (or minimizes) the number of vertices with outdegree at most W (or at least W). The problems’
computational complexities vary with W. In this paper we show several results related to their polynomial-time
approximability. |
キーワード |
(和) |
グラフ有向化 / 次数 / 貪欲法 / 近似(不)可能性 / / / / |
(英) |
graph orientation / degree / greedy algorithm / (in)approximability / / / / |
文献情報 |
信学技報, vol. 113, no. 371, COMP2013-58, pp. 123-130, 2013年12月. |
資料番号 |
COMP2013-58 |
発行日 |
2013-12-13 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2013-58 |