均等配分する多品種流問題の計算量
スポンサーリンク
概要
- 論文の詳細を見る
多品種流問題は,与えられたネットワーク上に複数の品種が与えられて,各品種を流出点から流入点へ所望の量だけ流すことができるかを判定する問題である.多品種流問題は通信網や交通網等多くの事例に応用でき,重要な問題であるため,効率的なあるアルゴリズムの研究がされている.しかし,現実の事例には種々の制約が付き,一般のアルゴリズムは適用できないことが多い.そういった制約の一つとして,各品種を流す路の集合を求めるのみで,求められた路に各品種ごとに均等に流れが割り当てられるような問題を考える.この問題は通信網の経路選択などに現れ,応用上重要であるが,過去理論的に扱われた例はほとんどない.本論文はこの問題の計算量を明らかにした.まず,一般的な場合に強NP完全に属することを示す.また品種数が固定でも2以上ならばNP完全であり,品種数が1の場合のみ多項式時間アルゴリズムが存在することを示す.次に,路の経由する枝数を2以下に限った問題も強NP完全であることを示し,この場合は品種数が任意の定数ならば多項式時間アルゴリズムが存在することを証明する.
- 社団法人電子情報通信学会の論文
- 1994-11-25
著者
関連論文
- ハラリイの一般化三並べ(新世代の計算限界-その解明と打破-招待解説論文)
- 無向グラフのk点連結性の検査
- H-彩色可能なグラフのクラスの階層構造のCirculant graphsによる細分化
- マルチホップ無線ネットワークにおける優先領域に基づく中継制御法(無線アドホックネットワーク技術論文特集)
- STOC2009参加報告
- DS-1-1 最大独立集合と最大マッチングに対する定数時間近似アルゴリズムの改善(DS-1. COMP学生シンポジウム,シンポジウムセッション)
- DS-1-14 飛び道具を考慮した逆算法に基づく詰将棋列挙技術(DS-1. COMP-NHC学生シンポジウム,シンポジウムセッション)
- スネーキーの置き石一つの必勝法
- 有向グラフにおけるk枝連結性の検査
- 部の大きさの比が高々定数倍の孤立2部クリークの列挙
- 目標枝連結度3の最大被覆供給点配置問題(ネットワークプロセッサ,通信のための信号処理,符号理論,一般)
- 毒まみれ半順序付き集合ゲームの必勝法(ネットワークプロセッサ,通信のための信号処理,符号理論,一般)
- 遺伝的な距離に基づいた家系図推定問題
- 孤立した部分グラフの列挙
- DNA配列のプローブ順序固定に必要な最小フラグメント集合
- 最短路ルーティングにおけるバックアップテーブルに関する考察
- LA-3 DNA配列におけるプローブの順序付けに必要な最小フラグメント集合(A. アルゴリズム・基礎)
- インターネットにおける経路ループの回避手法
- グラフの平面描画に関する3つの同値な尺度
- 端末のパケット中継機能を用いた安否確認ネットワークの検討(無線アドホックネットワーク技術論文特集)
- 加群上の畳込み符号による可変レートMPSK符号化変調方式
- 優先領域に基づく中継制御法を用いたマルチホップ無線ネットワークの検討
- B-5-205 マルチホップ無線ネットワークにおける優先領域に基づくルーチングプロトコルの検討
- B-5-204 通信可能時間を考慮したアドホックルーチングプロトコルの特性評価
- レイリーフェージング通信路に有効な環上の畳込み符号
- circulant制約を持った隣接色制約付き彩色問題の応用と解析 (計算理論とアルゴリズムの新展開)
- 位相情報を利用したDS-CDMA用干渉除去受信機特性
- B-5-149 ルーチングゾーンを用いた車々間通信プロトコル
- B-5-140 アドホックネットワークにおけるリンク間コストを考慮したルーチングプロトコル
- B-5-66 フェージング環境下における簡易受信方式の性能評価
- B-5-63 送信タイミング制御を用いたメディア統合予約型CDMAパケット通信方式
- B-5-7 フェージング環境における簡易干渉除去方式の性能評価
- B-5-6 フェージング通信路における位相情報を利用したDS-CDMA用干渉除去受信機特性
- SB-11-3 DS-CDMAシステムにおける簡易適応干渉除去方式
- B-5-169 メディア統合無線ネットワークにおける予約符号を用いたアクセス制御方式
- B-5-168 マルチホップ無線ネットワークにおける優先領域に基づくパケット中継制御法
- B-5-107 スペクトル拡散通信用簡易受信方式 : 簡易PN同期回路の並列接続による性能改善
- B-5-78 レイリーフェージング環境における位相情報を利用したDS-CDMA用干渉除去受信機特性
- 次数制限付最短路木に関する諸問題(グラフ・ネットワーク(2))
- 安否確認ネットワークにおける送信制御のパラメータの影響
- 音声・データ統合予約型パケット無線アクセス方式の検討
- 位相情報を利用したスペクトル拡散通信用干渉除去方式
- DS-CDMAシステムにおける適応干渉除去方式
- メディア統合予約型パケット無線アクセス方式におけるチャネル割り当て方式
- DS-CDMAにおけるMMSE法を用いた干渉除去方式
- サウンダー信号を持つBPSK変調方式の定包絡線化と特性解析
- k-NA枝連結かつ2-NA点連結な最小領域配置問題(グラフ・ネットワーク(1))
- 一般化詰め将棋問題の計算複雑さ : 小駒図式、成駒無し、還元玉、都詰の考慮
- B-5-122 スペクトル拡散通信用簡易受信方式
- B-5-110 スペクトル拡散通信用簡易干渉除去受信方式
- B-5-109 DS-CDMAシステムにおける干渉除去方式
- B-5-108 DS-CDMA システムにおける非直線特性を利用した干渉除去方式
- B-5-26 サウンダー信号を持つBPSK変調方式の定包絡線化
- ノード集中を除去する地図変形表示法(ORの実施)
- 再配置問題に対する線形時間移動手順決定法(グラフ・ネットワーク(1))
- ノード集中を解消するLP地図変形表示法
- ビデオオンデマンドにおけるプログラム再配置制御方式
- 再配置問題のグラフ論的性質(グラフ・ネットワーク(2))
- 毒まみれ半順序付き集合ゲームの必勝法(ネットワークプロセッサ,通信のための信号処理,符号理論,一般)
- 毒まみれ半順序付き集合ゲームの必勝法(ネットワークプロセッサ,通信のための信号処理,符号理論,一般)
- 平面グラフの^^^~-彩色問題
- Efficient Methods for Determining DNA Probe Orders(Discrete Mathematics and Its Applications)
- 目標枝連結度3の最大被覆供給点配置問題(ネットワークプロセッサ,通信のための信号処理,符号理論,一般)
- 目標枝連結度3の最大被覆供給点配置問題(ネットワークプロセッサ,通信のための信号処理,符号理論,一般)
- フロー割当てによるダイナミックルーチング網設計法
- ダイナミックルーチングのためのう回候補群作成法
- Query-Number Preserving Reductions and Linear Lower Bounds for Testing
- Inferring pedigree graphs from genetic distances
- グラフの変形操作における単純性の保存
- Special Section on Discrete Mathematics and Its Applications
- Maximum-Cover Source-Location Problems(Discrete Mathematics and Its Applications)
- 全節点・領域間がk-枝連結となる様に領域を決定する問題(グラフ・ネットワーク(1))
- フロー割当てによるネットワーク性能推定法
- 補グラフ入力に対する線形時間グラフ探索アルゴリズム(グラフ・ネットワーク(2))
- 補グラフ入力に対する線形時間グラフ探索アルゴリズム
- ジャンケンのトーナメント表現と意味のある拡張(アルゴリズムと計算量理論)
- 領域グラフにおける全節点・領域間のk-枝連結性の必要十分条件(グラフ・ネットワーク(1))
- 室田一雄編, 離散構造とアルゴリズムIII, 近代科学社, 1994, 204pp.
- 均等配分する多品種流問題の計算量
- 節点・領域間の2-枝連結性の線形時間判定法(グラフ・ネットワーク(1))
- T-混合カットにおける領域間連結度の性質(グラフ・ネットワーク(5))
- k-節点・領域連結問題の性質と解法
- 節点・領域連結問題とその絶対近似算法(組合せ最適化)
- 節点・領域間経路の性質と袋小路の解消法 : 2リンク迂回制限下での迂回可能経路数最大化法(組合せ最適化)
- フロー割当によるネットワーク性能推定法の評価
- 均等配分制約のある多品種流問題の計算量 : 多品種流路問題(情報・通信の流れ)
- 流量割当制約付き多品種流問題のPに属するクラス(グラフ・ネットワーク(1))
- 等間隔の折り目を持つ紙の折り畳みの計算量について
- An online algorithm optimally self-tuning to congestion for power management problems (コンピュテーション)
- ナップサック問題に対する定数時間近似アルゴリズム
- A-017 Multi-Commodity Source Location Problems and Price of Greed
- An almost optimal algorithm for Winkler's sorting pairs in bins (コンピュテーシヨン)
- ^^-Coloring Problem(Graphs and Networks)
- 「一般化三並べ」における未解決問題 (特集 続・解けそうで解けない問題)
- On H-Coloring Problems with H Expressed by Complements of Cycles, Bipartite Graphs, and Chordal Graphs(Special Section on Discrete Mathematics and Its Applications)
- An almost optimal algorithm for Winkler's sorting pairs in bins (Special issue : Theoretical computer science and discrete mathematics)
- ジャンケンの正しい一般化(パズルとゲームの計算理論)
- アルゴの国の時間の夢 (特集 時間とコンピュータ)
- 流量割当制約付き多品種流問題の強NP困難なクラス(組合せ・グラフ・ネットワーク)
- 経由枝数に制限をもつ多品種流問題