文献

J-GLOBAL ID：201402228868907595   整理番号：14A0161159

次数制約のあるグラフ有向化問題の近似について

Approximability of graph orientation problems with degree constraints

著者 (4件)： 朝廣雄一 (九州産大 情報科学) ,  JANSSON Jesper (京大 化研 バイオインフォマティクスセ) ,  宮野英次 (九州工大 大学院情報工学研究院) ,  小野廣隆 (九大 大学院経済学研究院)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 113  号： 371(COMP2013 38-59)  ページ： 123-130  発行年： 2013年12月13日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

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

シソーラス用語： *無向グラフ ,  有向グラフ ,  *近似法 ,  計算理論 ,  時間 ,  *方向制御 ,  最適化問題 ,  計算量 ,  計算機アルゴリズム
準シソーラス用語： 多項式時間 ,  貪欲法

分類 (2件)： 計算理論  (JB02000A) ,  グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (5件)： 次数 ,  制約 ,  グラフ ,  問題 ,  近似