Kリンク最短パス問題と行列探索
スポンサーリンク
概要
- 論文の詳細を見る
凹モンジュ性を持つ有向完全グラフのk個の辺を持つパスのうちで最短なものを求める効率の良いアルゴリズムを提案する.計算時間はO(n√<klogn>+nlogn)である.モンジュ性を持つ有向完全グラフの性質とともにパラメトリック探索が用いられる.応用として,(1)凸多角形に内接する最大のk角形(2)凸多角形に外接する最小のk角形(3)区間グラフの最大kクリーク(4)長さ限定最適コード(5)最適量子化の計算の高速化が得られる.
- 一般社団法人情報処理学会の論文
- 1994-01-25
著者
-
徳山 豪
日本アイ・ビー・エム東京基礎研究所
-
徳山 豪
日本IBM東京基礎研究所
-
Aggarwal Alok
IBM T.J. Watson Research Center
-
Schieber Baruch
IBM T.J. Watson Research Center
関連論文
- 多値属性を用いた最適なデータセグメンテーションを生成するアルゴリズム
- 幾何学アルゴリズムとその応用
- ランダムアルゴリズムの話題から
- 割り当て問題に対するランダムアルゴリズムの実験的検証
- 点集合の距離重複度列のノルムと最大部分集合問題
- 密な部分グラフ問題の貪欲解法
- 放物線のアレンジメントの組合せ複雑度について
- 割り当て問題に対するランダマイズド・アルゴリズムの実験的検証
- 線分族と三角形族の中での直交探索
- Kリンク最短パス問題と行列探索
- 三角形族の中での直交探索
- 単体内の点集合の分割について(LP新解法)
- パラメトリックなポリマトロイドとその幾何学的応用
- クラス間分散最大区間を求めるアルゴリズムと多次元への拡張
- イメージ切り出しに関するアルゴリズム
- 電子マネーシステムにおける最適なオンラインアルゴリズム
- 数値データからの直交凸領域結合ルール発見
- 領域及び区間分割を用いた決定木の作成 : 領域分割の有効性の検証
- データマイニングの最新動向 : 巨大データからの知識発見技術 (情報処理最前線)
- 最適区間問題と計算幾何学
- 平行移動する複数の点集合または線分集合に対するVoronoi図の複数さと文字配置への応用
- Euclid距離による凸多角形の多角形領域内へのmaximin配置問題とそれに関連した動的Voronoi図
- ヒッチコック型輸送問題の新算法
- A Unified Scheme for Detecting Fundamental Curves in Binary Edge Images
- 直線のアレンジメントの部分構成アルゴリズムと2色点集合の最適分割問題への応用