枝コストに制限を加えた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ネットワークの構成と利用(マルチメディアを利用したキャンパスネットワーク)
- IPのためのATMシグナリングプロトコルIP-SVC
- 可変通信速度PSK変復調器を利用したVSAT局間コンピュータネットワーク基礎実験
- ネットワーク仮想記憶を利用した連続メディアの伝送方式
- 枝コストに制限を加えたk-Canadian Traveller Problemの競合比解析 (コンピュテーシヨン)
- 最短路ルーティングにおけるバックアップテーブルに関する考察
- インターネットにおける経路ループの回避手法
- Host Identity Protocolを用いたロケーションプライバシを有する匿名移動通信(学生セッション)
- 複数手法によるリアルタイム解析を支援するトラヒックデータ配送システムの実装と評価(セキュリティ技術,セキュアでサステイナブルなインターネットアーキテクチャ論文)
- 機械学習によるネットワークIDSログデータの解析および可視化(インターネット応用及び一般)
- 未知の攻撃コードを安全に収集するための定点観測装置の構築手法(インターネット及び一般)
- 開放型大規模ネットワークのためのIDSログ監視支援システム(不正侵入・異常検知)(新たな脅威に立ち向かうコンピュータセキュリティ技術)
- 安全なギガビットネットワークシステムKUINS-IIIの構成とセキュリティ対策(ネットワーク管理)(インターネットアーキテクチャ技術論文)
- 公衆無線インターネット接続サービス「みあこネット」の設計と運用
- UPKI証明書自動発行検証プロジェクトのシステム移行における課題と対策(認証技術,インターネットと情報倫理教育,一般)
- SAML連携を用いてロケーションプライバシを守るeduroamアカウント利用方式(情報管理技術2,インターネットと情報倫理教育,一般)
- UPKIサーバ証明書プロジェクトにおける証明書自動発行支援システムの開発(認証技術,インターネットと情報倫理教育,一般)
- BS-8-3 オンデマンド型家庭内電力ネットワークのための電力ルーティングスイッチ(BS-8.情報通信とエネルギー管理の統合技術,シンポジウムセッション)
- BS-8-11 2部グラフ上での分担供給可能な割当て制限付き資源配分問題(BS-8.情報通信とエネルギー管理の統合技術,シンポジウムセッション)
- 公衆無線インターネットみあこネット3に対応したブロードバンドルータの実装(インターネット及び一般)
- VPNサーバを分散させた公衆無線インターネットみあこネット3の設計(インターネット及び一般)
- 自律分散型公衆無線インターネットアクセスサービスのセキュリティに関する考察(セッション5-A : 分散システム)
- UPKI証明書自動発行検証プロジェクトのシステム移行における課題と対策(認証技術,インターネットと情報倫理教育,一般)
- SAML連携を用いてロケーションプライバシを守るeduroamアカウント利用方式(情報管理技術2,インターネットと情報倫理教育,一般)
- 状況把握のためのトラヒック振舞い分類システムの構築と評価
- VPNサーバを分散させた公衆無線インターネットみあこネット3の設計(インターネット及び一般)
- 自律分散型公衆無線インターネットアクセスサービスのセキュリティに関する考察(セッション5-A : 分散システム)
- 国際会議SAINTの開催報告
- PR-SCTPを用いた高信頼性ストリーミング伝送(パラレル,インターネットと情報倫理教育,一般)
- PR-SCTPを用いた高信頼性ストリーミング伝送(パラレル,インターネットと情報倫理教育,一般)
- PR-SCTPを用いた高信頼性ストリーミング伝送(パラレル,インターネットと情報倫理教育,一般)
- 携帯電話からの遠隔カメラ制御の検討(MBL-2【携帯端末のアプリとその実行環境】)
- 携帯電話からの遠隔カメラ制御の検討(MBL-2【携帯端末のアプリとその実行環境】)
- BS-7-6 学術認証フェデレーションにおけるテレビ会議用MCUサービスの試験実装(BS-7.分散協調連携を支えるネットワークミドルウェア,シンポジウムセッション)
- オンデマンド型家庭内電力ネットワークのためのGMPLS型電力ルーティング
- オンデマンド型家庭内電力ネットワークのためのQoEn(エネルギー品質)を考慮した経路制御
- マジックプロトコル利用によるプライバシーに配慮したShibboleth属性交換の拡張
- マジックプロトコル利用によるプライバシーに配慮したShibboleth属性交換の拡張
- PR-SCTPをもちいたリアルタイム映像伝送における経路切り替え(インターネットアーキテクチャ技術-トランスポート、センサ、アプリケーション,インターネット、アプリケーション及び一般)
- NAS Parallel BenchmarksによるHPFの評価(並列計算)
- マルチプラットフォーム上でのHPFコンパイラの評価
- QoSネットワーク上のマルチキュースイッチにおけるオンラインバッファ管理アルゴリズムの競合比の改良析
- 新世代ネットワークにおけるオンデマンド型エネルギー配送サービスのためのQoEn(エネルギー品質)ルーティング(Future Internet,一般,Future Internet,一般)
- オンデマンド型電力ネットワークの設計と実装(学生セッション,学生セッション,一般)
- 第三者機関の仲介を必要としない配達証明付き電子メールシステムの設計(学生セッション,学生セッション,一般)
- 高精度なネットワーク侵入検知システムの構築(学生セッション,学生セッション,一般)
- みあこネットでの実時間動画像マルチキャスト実験
- みあこネットでの実時間動画像マルチキャスト実験
- UPKIサーバ証明書プロジェクトにおける証明書自動発行支援システムの開発(認証技術,インターネットと情報倫理教育,一般)
- SCTPにおけるアドレス選択ポリシーを定義できるIPアドレス自動更新機能の設計(インターネット技術及び一般I)
- SCTPにおけるアドレス選択ポリシーを定義できるIPアドレス自動更新機能の設計(インターネット技術及び一般I)
- 自律分散型公衆無線インターネットアクセスサービスのセキュリティに関する考察
- 未知の攻撃コードを安全に収集するための定点観測装置の構築手法(インターネット及び一般)
- BS-8-2 電力経路制御における電源側主導資源予約(BS-8.情報通信とエネルギー管理の統合技術,シンポジウムセッション)
- IPv6エンドツーエンドマルチホーミングのためのアドレス割当と送信元アドレスを考慮した経路制御(センサネットワーク,インターネット及び一般)
- IPv6エンドツーエンドマルチホーミングのためのアドレス割当と送信元アドレスを考慮した経路制御(センサネットワーク,インターネット及び一般)
- QoSルーティングにおけるメトリック情報の良し悪しに応じたLSAの時間間隔制限手法
- 動的に応答を変えるDNSを利用した電子メール受信の優先制御(電子メール,再考 分散システム/インターネットの運用・管理)
- アドレス情報の変更通知を集約できるようにするSCTP ADD-IP機能の改良(研究速報,ネクストジェネレーションに向けたインターネットアーキテクチャ論文)
- アドレス情報の変更通知を集約して再送できるようにするmSCTP拡張(インターネット及び一般)
- アドレス情報の変更通知を集約して再送できるようにするmSCTP拡張(インターネット及び一般)
- アドレス情報の変更通知を集約して再送できるようにするmSCTP拡張(インターネット及び一般)
- 複数アドレス対応のためのSocket API拡張(インターネット及び一般(2), インターネット及び一般)
- 複数アドレス対応のためのSocket API拡張(インターネット及び一般(2), インターネット及び一般)
- BS-8-3 UPKIプロジェクトにおけるオープンドメインサーバ証明書発行・導入(BS-8. セキュア、スケーラブルでサステイナブルなキャンパス情報システム,シンポジウムセッション)
- BS-8-2 UPKI共通仕様(アウトソースモデル)の提案(BS-8. セキュア、スケーラブルでサステイナブルなキャンパス情報システム,シンポジウムセッション)
- 大学間連携のための全国共同電子認証基盤UPKIにおける認証連携方式の検討(インターネット及び一般)
- 大学間連携のための全国共同電子認証基盤UPKIにおける認証連携方式の検討(インターネット及び一般)
- IPv6 end-to-end multihomingによるRSVPのモバイル対応(インターネット関連技術,及び一般)
- IPv6 end-to-end multihomingによるRSVPのモバイル対応(インターネット関連技術,及び一般)
- IPv6 end-to-end multihoming によるRSVPのモバイル対応
- 2ポート共有メモリ型スイッチにおけるオンラインバッファ管理アルゴリズムの厳密な競合比解析
- マルチキュースイッチにおけるオンラインバッファ管理アルゴリズムの競合比の改良(計算理論とアルゴリズムの新展開)
- 共有メモリ型スイッチにおけるオンラインバッファ管理アルゴリズムの競合比の改良
- 機械学習によるネットワークIDSログデータの解析および可視化(インターネット応用及び一般)
- 枝コストに制限を加えたk-Canadian Traveller Problemの競合比解析
- 段階的秘密交換プロトコルを利用した配達内容証明が可能な電子メール配送システム設計上の検討(学生セッション)
- サイクル上でのグラフ探索問題に対する最適なオンラインアルゴリズム
- 「大規模計算機シミュレーション特集号」を企画して(大規模計算機シミュレーション特集号)
- 不正を検出できるネットワーク軍人将棋
- 複数経路を活用したTCP-Friendlyなストリーミングシステムの設計と実装(インターネット応用及び一般)
- 複数経路を活用したTCP-Friendlyなストリーミングシステムの設計と実装(インターネット応用及び一般)
- ネットニュースサーバ群のトポロジーが持つスケールフリー性などの統計的性質(インターネット及び一般)
- ネットニュースサーバ群のトポロジーが持つスケールフリー性などの統計的性質(インターネット及び一般)
- 3. 次世代コンピュータに向けた技術課題と展望(スーパーコンピュータとプラズマ・核融合シミュレーションの発展とその将来)
- みあこネットでのマルチキャストを用いた映像配信実験
- みあこネットでのマルチキャストを用いた映像配信実験(モバイルと放送の融合の本格化を迎えて(1セグ放送,1/3セグラジオ放送,モバイル放送,携帯放送融合サービス,1/3セグ対応携帯端末,モバイルコンテンツと放送コンテンツの融合,マルチメディア配信,デジタル放送受信機,及び一般))
- BS-10-5 オンデマンド型家庭内直流送電網の設計と実装(BS-10.コンシューマ向けグリーンICTシステム,シンポジウムセッション)
- 情報通信・エネルギー統合技術の研究開発(エネルギーシステムの新展開-ICTによる消費情報の収集と利用)
- 第三者機関の仲介を必要としない配達証明付き電子メールシステムの設計
- 大学間認証連携のためのキャンパスPKI共通仕様(研究速報,スマートな社会を支えるインターネットアーキテクチャ論文)