容量付きネットワークのスリム化の計算複雑さについて(通信・情報(1))
スポンサーリンク
概要
- 論文の詳細を見る
制御不能流の理論[2.4]における無閉路2端子ネットワークの容量を,フローの実行可能性に影響を与えることなく減少させる(容量付きネットワークのスリム化)という問題を[11]において論じた.これに対して,一般の(有向閉路を含む)2端子ネットワークの場合"算法的困難が生じる"という主張に疑義が出された.そこで今回は,まず"一般のネットワークのスリム化"を正確に定義し直し,"スリム化の意義"を調べ,"一般の2端子ネットワークのスリム化の問題はNP-完全である"ことを示す.
- 社団法人日本オペレーションズ・リサーチ学会の論文
- 1997-04-02
著者
関連論文
- 標高データから得られる不変量について : 尾根と沢の抽出アルゴリズム
- 負極性沿面放電の進展モデルの解析解の導出
- 負極性直線状沿面放電の進展モデルとその解析解
- モデルを用いた放電のシミュレーション
- 沿面放電の進展条件の検討[2]-解析解の導出法
- 沿面放電進展の相転移的考察(4)
- 容量付きネットワークのスリム化の計算複雑さについて(通信・情報(1))
- 容量付きネットワークのスリム化について(グラフ・ネットワーク(2))
- 障害物のある領域における最短路の一計算法(交通・輸送(1))
- 局所地形解析, 傾向面分析, 最小二乗法, 微分
- 曲線の近似についての再考
- 高次元GISへの一つの道
- 応用数理の遊歩道(14) : 次元と行列に関する随想 II
- 応用数理の遊歩道(13) : 次元と行列に関する随想 I
- 論文の読み方[II ・ 完]
- 高橋秀俊,石橋善弘 : 電子計算機によるexactな計算の新方法(mod p演算の応用)(20世紀の名著名論)
- 地理情報システムにおけるデータ構造とアルゴリズム
- 日本応用数理学会創立十周年を迎えて(第10回年会総合講演より)
- 沿面放電進展の相転移的考察(3)
- 応用数理に関連する言語的諸問題(応用数理の遊歩道(15))
- 次元と行列に関する随想II(応用数理の遊歩道(14))
- 新世紀における空間データ基盤の役割(空間データ基盤の基礎と応用)
- 次元と行列に関する随想I(応用数理の遊歩道(13))
- 負極性直線状沿面放電モデルの検討
- 地理情報・空間データ基盤・OR