| 講演名 | 2014/11/13 次数制約のあるグラフ有向化問題の計算複雑さについて(グラフ,ペトリネット,ニューラルネット及び一般) 朝廣 雄一, ジャンソン ジェスパー, 宮野 英次, 小野 廣隆, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 無向グラフに対するオリエンテーション(グラフ有向化)とは,各辺に対して向き付けを行うことである.オリエンテーションによる結果として得られる有向グラフにおいて,各頂点の出次数が事前に指定された下界あるいは上界を満たす場合に,それを次数制約オリエンテーションと呼ぶ.本稿では,次数制約オリエンテーションを求める問題の一種である,2つのお互いに関連するMIN W-LIGHT問題とMAX W-HEAVY問題について考える.任意の固定された非負整数Wに対して,MIN W-LIGHT(またはMAX W-HEAVY)問題は,入力された無向グラフGのオリエンテーションのうち,出次数W以下(またはWP以上)の頂点数を最小化(または最大化)するものを発見することを目的とする.これらの問題の計算複雑さはWの値によって変化する.本稿では,これらの問題の計算複雑さ(主に近似可能性)に関するいくつかの結果を示す. |
| 抄録(英) | |
| キーワード(和) | |
| キーワード(英) | |
| 資料番号 | Vol.2014-AL-150 No.19 |
| 発行日 |
| 研究会情報 | |
| 研究会 | MSS |
|---|---|
| 開催期間 | 2014/11/13(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Mathematical Systems Science and its applications(MSS) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 次数制約のあるグラフ有向化問題の計算複雑さについて(グラフ,ペトリネット,ニューラルネット及び一般) |
| サブタイトル（和） | |
| タイトル（英） | |
| サブタイトル（和） | |
| キーワード(1)（和/英） | |
| 第 1 著者 氏名（和/英） | 朝廣 雄一 |
| 第 1 著者 所属（和/英） | 九州産業大学情報科学部 |
| 第 2 著者 氏名（和/英） | ジャンソン ジェスパー |
| 第 2 著者 所属（和/英） | 京都大学化学研究所バイオインフオマティクスセンター |
| 第 3 著者 氏名（和/英） | 宮野 英次 |
| 第 3 著者 所属（和/英） | 九州工業大学大学院情報工学研究院システム創成情報工学系 |
| 第 4 著者 氏名（和/英） | 小野 廣隆 |
| 第 4 著者 所属（和/英） | 九州大学大学院経済学研究院経済工学部門 |
| 発表年月日 | 2014/11/13 |
| 資料番号 | Vol.2014-AL-150 No.19 |
| 巻番号（vol） | vol.114 |
| 号番号（no） | 313 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |