枝コストに制限を加えたk-Canadian Traveller Problemの競合比解析
スポンサーリンク
概要
- 論文の詳細を見る
オンライン問題の一つにk-Canadian Traveller Problem (k-CTP)がある.k-CTPとは,枝に重みの付いたグラフG=(V,E)上の与えられた頂点sからtまでの最短経路問題である.オンラインアルゴリズムは前もってグラフの構造と全ての枝のコストを知っている.しかし,グラフ上で高々κ個の枝が封鎖されており,枝が封鎖されているか否かはその枝に隣接する頂点に辿り着いた時に初めて分かる.Westphalは任意のグラフに対して,競合比が2k+1になることを示した.本稿では,枝コストに制限をかけた場合のk-CTPの競合比解析を行う.具体的には,完全グラフに対し,枝コストが全て1の場合,枝コストが三角不等式を満たす場合に対して,それぞれ競合比が(k+1)/2,kになることを示す(グラフの連結性を保証するために,全封鎖数kは|V|-2以下とする).
- 社団法人電子情報通信学会の論文
- 2010-01-18
著者
-
岡部 寿男
京都大学学術情報メディアセンター
-
宮崎 修一
京都大学学術情報メディアセンター
-
岡部 寿男
京都大学
-
福田 剛士
京都大学大学院情報学研究科
-
宮崎 修一
京都大学 学術情報メディアセンター
関連論文
- 状況把握のためのトラヒック振舞い分類システムの構築と評価(ネットワーク管理・オペレーション,システム開発・ソフトウェア開発論文)
- 公衆無線インターネット接続サービス「みあこネット」の設計と運用(ネットワーク管理・オペレーション)
- 様々なアプリケーションへの攻撃活動を察知する汎用性の高いハニーポットシステムの構築と運用(ネットワークセキュリティ,インターネット技術とその応用論文)
- Chapter 4 オンデマンド型家庭内電力ネットワークのためのQoEn(エネルギー品質)を考慮した経路制御(制御・通信プロトコル,エネルギーの情報化〜ITによる電力マネジメント〜)
- 制御・通信プロトコル オンデマンド型家庭内電力ネットワークのためのQoEn(エネルギー品質)を考慮した経路制御 (特集 エネルギーの情報化--ITによる電力マネジメント)
- 家庭内電力ネットワークにおけるQoEnを考慮した電力制御の提案(学生セッション,一般)
- IDS警報の解析による第三者機関への攻撃状況の把握手法(学生セッション,一般)
- 迅速な障害対応を支援するトラヒック可視化システムの構築と評価(ネットワーク管理・オペレーション,システム開発・ソフトウェア開発論文)
- FECとPath-Diversityを利用した回復可能なストリーミング(セッション4 : マルチメディア通信とその応用)
- 京都大学におけるATMネットワークの構成と利用(マルチメディアを利用したキャンパスネットワーク)