@techreport{oai:ipsj.ixsq.nii.ac.jp:00106911,
 author = {朝廣雄一 and ジャンソンジェスパー and 宮野英次 and 小野廣隆},
 issue = {19},
 month = {Nov},
 note = {無向グラフに対するオリエンテーション （グラフ有向化） とは，各辺に対して向き付けを行うことである．オリエンテーションによる結果として得られる有向グラフにおいて，各頂点の出次数が事前に指定された下界あるいは上界を満たす場合に，それを次数制約オリエンテーションと呼ぶ．本稿では，次数制約オリエンテーションを求める問題の一種である，2 つのお互いに関連する Min W-Light 問題と Max W-Heavy 問題について考える．任意の固定された非負整数 W に対して，Min W-Light （または Max W-Heavy） 問題は，入力された無向グラフ G のオリエンテーションのうち，出次数 W 以下 （または W 以上） の頂点数を最小化 （または最大化） するものを発見することを目的とする．これらの問題の計算複雑さは W の値によって変化する．本稿では，これらの問題の計算複雑さ （主に近似可能性） に関するいくつかの結果を示す．},
 title = {次数制約のあるグラフ有向化問題の計算複雑さについて},
 year = {2014}
}