WEKO3
アイテム
次数制約のあるグラフ有向化問題の計算複雑さについて
https://ipsj.ixsq.nii.ac.jp/records/106911
https://ipsj.ixsq.nii.ac.jp/records/1069115ddde17b-244d-4dbf-bced-45357a43aef0
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL14150019.pdf (481.1 kB)
|
Copyright (c) 2014 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2014-11-13 | |||||||||||||
| タイトル | ||||||||||||||
| タイトル | 次数制約のあるグラフ有向化問題の計算複雑さについて | |||||||||||||
| 言語 | ||||||||||||||
| 言語 | jpn | |||||||||||||
| 資源タイプ | ||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||||||
| 資源タイプ | technical report | |||||||||||||
| 著者所属 | ||||||||||||||
| 九州産業大学情報科学部 | ||||||||||||||
| 著者所属 | ||||||||||||||
| 京都大学化学研究所バイオインフォマティクスセンター | ||||||||||||||
| 著者所属 | ||||||||||||||
| 九州工業大学大学院情報工学研究院システム創成情報工学系 | ||||||||||||||
| 著者所属 | ||||||||||||||
| 九州大学大学院経済学研究院経済工学部門 | ||||||||||||||
| 著者名 |
朝廣雄一
× 朝廣雄一
× ジャンソンジェスパー
× 宮野英次
× 小野廣隆
|
|||||||||||||
| 論文抄録 | ||||||||||||||
| 内容記述タイプ | Other | |||||||||||||
| 内容記述 | 無向グラフに対するオリエンテーション （グラフ有向化） とは，各辺に対して向き付けを行うことである．オリエンテーションによる結果として得られる有向グラフにおいて，各頂点の出次数が事前に指定された下界あるいは上界を満たす場合に，それを次数制約オリエンテーションと呼ぶ．本稿では，次数制約オリエンテーションを求める問題の一種である，2 つのお互いに関連する Min W-Light 問題と Max W-Heavy 問題について考える．任意の固定された非負整数 W に対して，Min W-Light （または Max W-Heavy） 問題は，入力された無向グラフ G のオリエンテーションのうち，出次数 W 以下 （または W 以上） の頂点数を最小化 （または最大化） するものを発見することを目的とする．これらの問題の計算複雑さは W の値によって変化する．本稿では，これらの問題の計算複雑さ （主に近似可能性） に関するいくつかの結果を示す． | |||||||||||||
| 書誌レコードID | ||||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||||
| 収録物識別子 | AN1009593X | |||||||||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2014-AL-150, 号 19, p. 1-8, 発行日 2014-11-13 |
|||||||||||||
| Notice | ||||||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||||||
| 出版者 | ||||||||||||||
| 言語 | ja | |||||||||||||
| 出版者 | 情報処理学会 | |||||||||||||
