講演名 | 2000/11/2 無向フローネットワークのminimax実現に関する問題のNP完全性について 田村 裕, 仙石 正和, 篠田 庄司, 阿部 武雄, |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | 与えられた行列を2点間の最大流量として無向フローネットワーク上へ実現する問題は, 従来より研究されてきており, さまざまな結果が得られている.筆者らは以前に, 各2点間にフローネットワーク上に実現できるとは限らない価(要求値)を与えた場合に, その実現となる無向フローネットワークにおける最大流量との差を最小とする問題について考察し, その実現法について述べた.本報告ではこの「差」の概念を一般化した実現に関連する問題の一部がNP完全であることを示す. |
抄録(英) | We consider a realization problem of an undirected flow network N from a matrix M. We assume that M is not always a terminal capacity matrix. In this condition, we considered problems to minimize differences between capacities between vertex pairs in N, and elements of M in previous papers. In this paper, we generalize the concept of difference and we show that a part of a problem related minimax realization problems is NP-complete. |
キーワード(和) | グラフ理論 / フローネットワーク / 端子容量行列 / 実現問題 / NP完全 |
キーワード(英) | graph theory / flow network / terminal capacity matrix / realization problem / NP-complete |
資料番号 | CAS 2000-63,CST 2000-18 |
発行日 |
研究会情報 | |
研究会 | CST |
---|---|
開催期間 | 2000/11/2(から1日開催) |
開催地(和) | |
開催地(英) | |
テーマ(和) | |
テーマ(英) | |
委員長氏名(和) | |
委員長氏名(英) | |
副委員長氏名(和) | |
副委員長氏名(英) | |
幹事氏名(和) | |
幹事氏名(英) | |
幹事補佐氏名(和) | |
幹事補佐氏名(英) |
講演論文情報詳細 | |
申込み研究会 | Concurrent System Technology (CST) |
---|---|
本文の言語 | JPN |
タイトル(和) | 無向フローネットワークのminimax実現に関する問題のNP完全性について |
サブタイトル(和) | |
タイトル(英) | NP-completeness of a minimax realization problem on undirected flow networks |
サブタイトル(和) | |
キーワード(1)(和/英) | グラフ理論 / graph theory |
キーワード(2)(和/英) | フローネットワーク / flow network |
キーワード(3)(和/英) | 端子容量行列 / terminal capacity matrix |
キーワード(4)(和/英) | 実現問題 / realization problem |
キーワード(5)(和/英) | NP完全 / NP-complete |
第 1 著者 氏名(和/英) | 田村 裕 / Hiroshi TAMURA |
第 1 著者 所属(和/英) | 新潟工科大学情報電子工学科 Dept. of Information and Electronics Engineering, Niigata Institute of Technology |
第 2 著者 氏名(和/英) | 仙石 正和 / Masakazu SENGOKU |
第 2 著者 所属(和/英) | 新潟大学工学部情報工学科 Faculty of Engineering, Niigata University |
第 3 著者 氏名(和/英) | 篠田 庄司 / Shoji SHINODA |
第 3 著者 所属(和/英) | 中央大学理工学部電気電子情報通信工学科 Faculty of Science and Engineering, Chuo University |
第 4 著者 氏名(和/英) | 阿部 武雄 / Takeo ABE |
第 4 著者 所属(和/英) | 新潟工科大学情報電子工学科 Dept. of Information and Electronics Engineering, Niigata Institute of Technology |
発表年月日 | 2000/11/2 |
資料番号 | CAS 2000-63,CST 2000-18 |
巻番号(vol) | vol.100 |
号番号(no) | 417 |
ページ範囲 | pp.- |
ページ数 | 8 |
発行日 |