無向フローネットワークのminimax実現に関する問題のNP完全性について
スポンサーリンク
概要
- 論文の詳細を見る
与えられた行列を2点間の最大流量として無向フローネットワーク上へ実現する問題は, 従来より研究されてきており, さまざまな結果が得られている.筆者らは以前に, 各2点間にフローネットワーク上に実現できるとは限らない価(要求値)を与えた場合に, その実現となる無向フローネットワークにおける最大流量との差を最小とする問題について考察し, その実現法について述べた.本報告ではこの「差」の概念を一般化した実現に関連する問題の一部がNP完全であることを示す.
- 社団法人電子情報通信学会の論文
- 2000-11-02
著者
-
篠田 庄司
中央大学理工学部電気電子情報通信工学科
-
田村 裕
新潟工科大学工学部情報電子工学科
-
仙石 正和
新潟大学工学部情報工学科
-
阿部 武雄
新潟工科大学情報電子工学科
-
篠田 庄司
中央大学理工学部
-
田村 裕
新潟工科大学工学部
-
仙石 正和
新潟大学工学部
-
阿部 武雄
新潟工科大学
-
阿部 武雄
新潟大
-
田村 裕
新潟工科大学
関連論文
- 並列分散システムにおけるデータ配信アルゴリズム (VLSI設計技術)
- 並列分散システムにおけるデータ配信アルゴリズム (回路とシステム)
- マルチホップ無線ネットワークにおける端末の移動による中継端末の変化に関する考察
- 無線通信におけるネットワークコーディングを用いた情報転送の効率化について
- A-1-18 格子状マルチホップ無線ネットワークにおける最適経路のホップ数(A-1.回路とシステム,一般セッション)
- マルチホップ無線網における移動体流の情報運搬能力に関する考察
- マルチホップ無線網における経路MTMの解析
- 1次元マルチホップ無線網における経路選択手法のETXの近似解析手法の評価
- マルチホップ無線ネットワークのアクセスポイントへ接続する端末数について
- AS-1-1 ネットワークコーディングに関連したグラフの辺彩色問題(AS-1. グラフ理論と組合せアルゴリズム,シンポジウムセッション)
- 格子状マルチホップ無線ネットワークにおける経路ETXの解析
- マルチホップ無線ネットワークにおける経路品質の解析(グラフ,ペトリネット,ニューラルネット及び一般)
- マルチホップ無線網におけるホップ数と中継負荷を考慮した中継局配置手法に関する考察(セキュリティ,信頼性,モバイル,一般)
- B-21-52 アドホックネットワークにおけるウイルスの広がりに関する考察(B-21.アドホックネットワーク, 通信2)
- B-21-3 マルチホップセルラネットワークにおける最適化問題に関する考察(B-21.アドホックネットワーク, 通信2)
- オンデマンド型ルーティングにおけるトラフィックを考慮した再構築方法
- ネットワークコーディングとグラフの辺彩色問題について(グラフ,ペトリネット,ニューラルネット及び一般)
- ある種の並列分散システムにおけるブロードキャストスケジューリング(グラフ,ペトリ,ニューラルネット及び一般)
- 広域並列分散システムのブロードキャストスケジューリングについて(グラフとネットワーク)
- 最新グラフネットワーク理論とその応用
- 異動クラスタシステムのブロードキャストスケジューリングに関する一考察
- [招待論文]グラフ理論,確率幾何学の移動通信への応用
- マルチホップ無線通信におけるチャネル割当に関する一考察
- 無向フローネットワークのminimax実現問題のある一般化について
- 拡張された辺彩色問題の点彩色問題への変換について
- 拡張された辺彩色問題の点彩色問題への変換について(研究速報)
- いくつかの要求を満足する無向フローネットワークの実現について
- フローネットワークのロケーション問題の一考察
- B-5-66 高速移動 OFDM 無線伝送方式における量子化誤差の検討
- 並列分散システムにおけるデータ配信アルゴリズム(システムと信号処理及び一般)
- 並列分散システムにおけるデータ配信アルゴリズム(システムと信号処理及び一般)
- CAS2010-4 並列分散システムにおけるデータ配信アルゴリズム(システムと信号処理及び一般)
- 並列分散システムにおけるデータ配信アルゴリズム(システムと信号処理及び一般)
- B-5-142 センサネットワークのための二段階ルート構築手法
- JABEEへの電子情報通信学会の対応(JABEEの審査と認定への申請に向けて : 評価と認定で包囲されつつある高等教育機関,対応は十分か?)
- J-035 適応的ビーム分割による高周波電磁波伝搬の高速可視化(J分野:グラフィクス・画像)
- 3次元立体視装置を用いた都市空間中の対話的電磁波伝搬の可視化について
- B-15-9 Bluetooth 端末を用いた屋内位置検出システムの構築
- JABEEに認定申請するためにはどうしたらよいのか : 学部における技術者教育システムの改善と発展のために(JABEEの審査と認定への申請に向けて : 評価と認定で包囲されつつある高等教育機関,対応は十分か?)
- Bluetooth を用いた情報配信方法の一検討
- ユニバーサル・アドホックネットワークの検討 : PHSを2台用いた送受信方式の情報配信実験
- 電波伝搬ビジュアル・シミュレーションのための適応的ビーム・トレーシングの改良
- マルチホップ無線網における移動体流の情報運搬能力に関する考察
- B-7-22 端末間直接通信と端末の移動の関係についての考察
- A-1-35 二次元ランダムマルチホップ無線ネットワークにおけるホップ数最小の経路の通信品質(A-1.回路とシステム,一般セッション)
- 二次元ランダムマルチホップ無線ネットワークにおける最適経路の特徴づけ
- A-1-13 格子状マルチホップ無線網における最小経路MTMの解析(A-1. 回路とシステム,一般セッション)
- マルチホップ無線網における経路MTMの解析
- マルチホップ無線ネットワークにおける経路品質の解析(グラフ,ペトリネット,ニューラルネット及び一般)
- Bluetooth 機器間における認識時間の検討
- PHSを用いたネットワーク内の端末認識方法に関する研究
- 呼量変動時におけるオーバーレイシステムの性能評価
- 移動速度と方向の情報を用いたダイナミックチャネル割当のシミュレーション評価
- ネットワークコーディングとグラフの辺彩色問題について(グラフ,ペトリネット,ニューラルネット及び一般)
- 3次元空間における電波伝搬ビジュアル・シミュレーション
- 地理情報に基づいた電磁波伝搬の可視化
- 簡略化適応可変型ゾーン構成システムにおけるダイナミックチャネル割当て方式の適用効果に関する一検討
- SA-6-6 セルラ移動通信と割当問題
- ネットワークにおけるある種の配送問題について
- 遺伝的アルゴリズムを用いたセルラ移動通信系におけるダイナミックチャネル割当に関する一考察
- 道路網における移動体の流れと移動通信トラヒック
- 道路網における移動体の流れと移動通信トラヒック
- AS-3-13 エピデミック伝送における送信を制限した場合の情報伝達特性の解析(AS-3.安全・安心な生活のための情報通信技術,シンポジウムセッション)
- A-1-30 マルチホップ無線網におけるホップ数と消費電力の関係について(A-1.回路とシステム,一般セッション)
- 同期距離のマークグラフ上への実現について
- B-21-11 ルーティングプロトコルにおける効果的な位置情報の利用に関する検討(B-21.アドホックネットワーク, 通信2)
- ある種の並列分散システムにおけるブロードキャストスケジューリング(グラフ,ペトリ,ニューラルネット及び一般)
- マルチホップ無線通信におけるチャネル割当に関する一考察
- 新会長からのメッセージ
- 無向フローネットワークのminimax実現に関する問題のNP完全性について
- 無向フローネットワークのminimax実現に関する問題のNP完全性について
- ユニバーサルアドホックネットワークにおける情報配信アルゴリズムのグラフ理論的考察
- 彩色ネットワークにおけるリソース数の最小化について
- アドホックネットワークにおける情報配信問題へのグラフ理論的アプローチ
- アドホックネットワークにおける情報配信問題へのグラフ理論的アプローチ
- ユニバーサル・アドホックネットワークの検討 : 木状ネットワークに対する情報配信アルゴリズム
- グラフ・ネットワーク理論の倉庫の片隅に積まれている問題
- 端子容量行列とは限らない行列からの無向フローネットワークの実現について
- 無向フローネットワークのminimax実現問題の一般化について
- グラフ・ネットワーク理論とその応用の今後
- いくつかの要求を満足する無向フローネットワークの実現について
- 基礎・境界ソサイエティの活性化の一活動 : ICFS 2002の活動計画
- 端子容量行列を実現するフローネットワークの構造
- 端子容量行列を実現するネットワークのもつ構造について
- 端子容量行列を実現するネットワークのもつ構造について(グラフ,ネットワークとアルゴリズムおよび一般)
- オンデマンド型ルーティングにおける安定ルートの構築
- 21世紀への回路理論の基礎[III] : パラメータ値算定
- 木状の内部点を持つ線形受動抵抗回路の素子値算定可能性の必要十分条件
- 実効値測定による点電位の算定法
- A-29 実効値測定による点電位の算定法(A-1. 回路とシステムD,一般講演)
- マルチホップ無線網における共通の点を持たない複数の経路に関する一考察
- マルチホップ無線網における共通の点を持たない複数の経路に関する一考察
- マルチホップ無線網における共通の点を持たない複数の経路に関する一考察
- マルチホップ無線網における共通の点を持たない複数の経路に関する一考察
- マークグラフ上へ実現可能な同期距離の性質について
- マークグラフ上へ実現可能な同期距離の性質について
- 高速道路用チャネルを設定したダイナミックチャネル割当法の性能評価
- 線形RLC回路の短絡故障診断の基礎理論
- ユニバーサル・アドホックネットワークの検討 : PHSを2台装備する端末の接続制御方式
- 移動通信系の通信トラヒックのモデルについて