2段階転送コストを持つ,パス構造ネットワークでの最適なfile transferの構成について (II)
スポンサーリンク
概要
- 論文の詳細を見る
ファイル複製ネットワークN上の最適なfile transferを求める問題とは,ある情報ファイルのコピーを,幾つかの点から各点に需要値分の部数だけ,最小総コストで提供する方法を考えることである.一般的なNに対して,本問題はNP困難であるが,多項式時間のアルゴリズムで最適なfile transferが求められるような特殊なNのクラスも知られている.これまで,扱ってきたNにおいては,各点間の転送コストが線形であるという条件があった.実用的な問題を考えると,転送コストが階段である場合も無視できない.もちろん,このような問題も本質的にNP困難であることが証明されている.本報告では,この問題を多項式時間で解くための第一歩として,構造がパスグラフであり,各点の需要値が全て1であり,転送(枝)コストが2段階であるものを考える.その結果,この問題が多項式時間で解けることを示す.
- 社団法人電子情報通信学会の論文
- 1999-11-09
著者
関連論文
- 2-F-2 打鍵回数で分類した連打鍵集合による個人認証について(モデリング)
- A-15-5 3種類の2連打鍵による個人認識について(A-15.ヒューマン情報処理,一般講演)
- 大規模な一個人打鍵情報による,小規模な参照データに対する個人の特定
- A-7-5 打鍵認証でのUW法におけるdigraphの選択について(A-7. 情報セキュリティ,一般セッション)
- 発進局選択での最適なfile transferの構成について
- 発進局選択での最適なfile transferの構成について
- 発進局選択での最適なfile transferの構成について
- 発進局選択での最適なfile transfer の構成について
- 創立40周年記念式典・中部支部シンポジウムルポ
- シミュレーティッド・アニーリングを用いたfile transferの構成法について
- マルチプロセッサスケジューリング問題における近傍解の構成法について
- simple tree-out & tree-in型クスクグラフスケジューリング問題の一考察
- 大規模高速データ転送並列処理システムに対するスケジューリングアルゴリズム
- 論文発表プログラム自動作成ソフトウェア「江戸っ子」 : 偏りある割り当てへの対応(デモ展示・ポスター講演,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 論文発表プログラム自動作成ソフトウェア「江戸っ子」 : 偏りある割り当てへの対応(デモ展示・ポスター講演,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- 論文発表プログラム自動作成ソフトウェア「江戸っ子」 : 偏りある割り当てへの対応(デモ展示・ポスター講演,ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- キーストロークダイナミクスでの評価関数の切替手法について(グラフ,ペトリネット,ニューラルネット及び一般)
- キーストロークダイナミクスでの評価関数の切替手法について(グラフ,べトリネット,ニューラルネット及び一般)
- 固定ルート上の情報ファイルの転送方法を求める線形時間のアルゴリズムについて
- 固定ルート上の情報ファイルの転送方法を求める線形時間のアルゴリズムについて
- ファイル加工ネットワーク上の最速のファイル圧縮転送について
- 非圧縮転送を考慮した,固定ルート上のファイルの最適な圧縮転送について(ネットワーク(1))
- ルートが固定された2点間の最短時間のファイル圧縮転送について
- 最短時間のファイル圧縮転送を与える2点を決定する線形時間のアルゴリズムについて
- 区間グラフ上の頂点のbetweennes値について
- 梯子型ネットワークの最短路を求める線形時間アルゴリズム
- 情報ファイルの最速な圧縮転送を求める2つの線形時間アルゴリズム
- はしご型構造のネットワークの最短路問題について
- B-21-9 アドホックネットワークでの経路探索での容量モデル活用(B-21.アドホックネットワーク,一般セッション)
- スタティックなアドホックネットワークにおけるシンクルーティングについて--ネットワークフローへの帰着 (アドホックネットワーク)
- An Optimal File Transfer on an Undirected Path Network with 2-level Arc Cost
- An Optimal File Transfer on an Undirected Path Network with 2-level Arc Cost
- 複製コストが増加するネットワークに対する最適なfile transferの構成について(グラフ,ペトリ,ニューラルネット,及び一般)
- 複製コストが増加するネットワークに対する最適なfile transferの構成について(グラフ,ペトリ,ニューラルネット,及び一般)
- 複製コストが増加するネットワークに対する最適な file transfer の構成について
- グラフを使った, 順序つきデータのコンセンサス作成法について
- グラフを使った, 順序つきデータのコンセンサス作成法について
- 発信局2個の2段階転送コストを持つパスネットワークにおける最小コストのファイル転送方法について(グラフ・ネットワーク(1))
- プログラミング演習としてのグラフ・ネットワーク理論
- 2段階転送コストを持つ, パス構造ネットワークでの最適なfile transferの構成について(III)
- 2段階転送コストを持つ,パス構造ネットワークでの最適なfile transferの構成について (II)
- 2段階転送コストを持つ,パス構造ネットワークでの最適なfile transferの構成について (II)
- B-18-3 A new dissimilarity measure in keystroke dynamics
- 2段階の転送コストを持つネットワークシステムでの最適な情報ファイルの転送について
- 2段階の転送コストを持つネットワークシステムでの最適な情報ファイルの転送について
- 2個の始点を持つファイル転送ネットワークの最適なファイルスケジューリングの構成について
- 2-中継点網の構成問題について
- ネットワークにおける,ファイル複製・転送総コストが最小となるための発信局設定について(グラフ・ネットワーク(2))
- 2段階転送コストを持つ, バス構造ネットワークでの最適なfile transferの構成について(I)
- 各点の需要値が高々1であるネットワークでの最適なfile transferの構成について
- 2段階転送コストを持つ,パス構造ネットワークでの最適なfile transferの構成について(2)
- オリジナルファイルを任意部数持つネットワークでの最適なファイル転送について
- ファイル転送ネットワークにおける枝の本数に制限のある最適なfile transferについて(II)
- ハミング距離似のフィルタリングを用いたキーストロークダイナミクスによるパスワード強化
- ハミング距離似のフィルタリングを用いたキーストロークダイナミクスによるパスワード強化
- 木構造のファイル複製ネットワークの最適な2 : ファイルスケジューリングについて
- ファイル転送ネットワーク上の最適な2-ファイルスケジューリングについて
- 1-H-1 Multi-data filtering method in keystroke dynamics-based user authentication
- ハミング距離似のフィルタリングを用いたキーストロークダイナミクスによるパスワード強化
- ソースファイルが点在するネットワーク上の森型ファイル転送の最適性について
- オリジナルファイルが任意部数与えられたファイル転送ネットワーク上の最適なfile transferの構成について(グラフ,ネットワークとアルゴリズムおよび一般)