文献

J-GLOBAL ID：201502228954483754   整理番号：15A0192621

次数制約のあるグラフ有向化問題の計算複雑さについて

著者 (4件)： 朝廣雄一 (九州産大 情報科学) ,  ジェスパー ジャンソン (京大 化研 バイオインフォマティクスセ) ,  宮野英次 (九州工大 大学院情報工学研究院) ,  小野廣隆 (九大 大学院経済学研究院)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 114  号： 312(CAS2014 87-104)  ページ： 105-112  発行年： 2014年11月13日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 短報  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 無向グラフに対するオリエンテーション(グラフ有向化)とは,各辺に対して向き付けを行うことである。オリエンテーションによる結果として得られる有向グラフにおいて,各頂点の出次数が事前に指定された下界あるいは上界を満たす場合に,それを次数制約オリエンテーションと呼ぶ。本稿では,次数制約オリエンテーションを求める問題の一種である,2つのお互いに関連するMIN W-LIGHT問題とMAX W-HEAVY問題について考える。任意の固定された非負整数Wに対して,MIN W-LIGHT(またはMAX W-HEAVY)問題は,入力された無向グラフGのオリエンテーションのうち,出次数W以下(またはW以上)の頂点数を最小化(または最大化)するものを発見することを目的とする。これらの問題の計算複雑さはWの値によって変化する。本稿では,これらの問題の計算複雑さ(主に近似可能性)に関するいくつかの結果を示す。(著者抄録)

シソーラス用語： *有向グラフ ,  無次元数 ,  *計算量 ,  頂点 ,  無向グラフ ,  次数

分類 (1件)： グラフ理論基礎  (IA02020S)

引用文献 (23件)：

• Asahiro, Y., Jansson, J., Miyano, E., and Ono, H.: Upper and lower degree bounded graph orientation with minimum penalty. In Proc. of CATS 2012, CRPIT Series, Vol. 128, 139-146, 2012.
• Asahiro, Y., Jansson, J., Miyano, E., and Ono, H.: Graph orientations optimizing the number of light or heavy vertices. In Proc. of ISCO 2012, LNCS, Vol. 7422, 332-343, 2012.
• 朝廣雄一, ジェスパージャンソン, 宮野英次, 小野廣隆: 次数制約のあるグラフ有向化問題の近似について. 電子情報通信学会コンピュテーション研究会, 信学技報, Vol.113, No.371, COMP2013-58, pp.123-130, 2013 年 12 月.
• Asahiro, Y., Jansson, J., Miyano, E., Ono, H., and Zenmyo, K: Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree. Journal of Combinatorial Optimization 22(1) 78-96, 2011.
• Chlebik, M. and Chlebikova, J.: Complexity of approximating bounded variants of optimization problems. Theor. Comput. Sci. 354(3), 320-338, 2006.

タイトルに関連する用語 (5件)： 次数 ,  制約 ,  グラフ ,  問題 ,  計算複雑さ