グラフアルゴリズム
| アルゴリズム | 提供者 | 提供形態 | 必要環境 | 動作確認 |
|---|---|---|---|---|
| グラフ・ネットワーク表現のデータ構造 | ||||
| 隣接リスト | ||||
| 隣接行列 | ||||
| implicit表現（幾何的表現、区間表現、 交グラフ表現、補グラフ表現等） |
||||
| その他 | ||||
| グラフ探索 | ||||
| 深さ優先 | ||||
| 幅優先 | ||||
| トポロジカルソート | ||||
| 基本グラフアルゴリズム | ||||
| 強連結成分分解 | ||||
| 2連結成分分解 | ||||
| 2部グラフのマッチング Hopcroft-Karp | ||||
| DM分解 | ||||
| グラフのスパース化 | 中村秀司 （豊橋技術科学大学） |
Cソース | C汎用 | Linux(egcs-1.1.2) |
| 基本ネットワークアルゴリズム | ||||
| 最小スパンニング木 Kruskal, Prim, Yao (round robin) | ||||
| 最短パス Dijkstra, Warshall-Floyd | ||||
| 最大フロー Dinic, Goldberg-Tarjan | ||||
| 最適割り当て Edmonds-Karp(Tomizawa) | ||||
| グラフ・ネットワークアルゴリズムをサポートするデータ構造 | ||||
| ヒープ, dヒープ | ||||
| Fヒープ | ||||
| 2色木(red black tree), splay木 | ||||
| set union-find tree | ||||
| dynamic tree | ||||
| 区間木、区分木 | ||||
| ヒープ探索木(priority search tree) | ||||
| 残存探索木(persistent search tree) | ||||
| アルゴリズム | 提供者 | 提供形態 | 必要環境 | 動作確認 |
|---|---|---|---|---|
| 最小カットアルゴリズム | ||||
| Nagamochi-Ibaraki | 永持 仁 （京都大学） |
webデモ |
||
| Augmentation | ||||
| グラフの最小カットのカクタス表現 | 中村 秀司 （豊橋技術科学大学） |
Cソース | C汎用 | Linux egcs-1.1.2 |
| グラフの辺連結度増大関数 | 阿部 勇介 （豊橋技術科学大学） |
Cソース webデモ  |
C汎用 | Linux egcs-1.1.2 |
| 供給点配置問題 | 阿部 勇介 （豊橋技術科学大学） |
Cソース | C汎用 | Linux egcs-1.1.2 |
| 最大フローアルゴリズム | ||||
| 有向ネットワーク Goldberg-Rao | 浅野 孝夫 （中央大学） |
|||
| 無向グラフ Karger | 浅野 孝夫 （中央大学） |
|||
| 最小費用フローアルゴリズム | ||||
| Edmonds, Orlin-Plotkin-Tardos | 浅野 孝夫 （中央大学） |
|||
| アルゴリズム | 提供者 | 提供形態 | 必要環境 | 動作確認 |
|---|---|---|---|---|
| 平面グラフ | ||||
| 最短非交差道(林)アルゴリズム | 蒲倉 正憲 （東北大学） |
実行形式 | MS-Win Visual C++ LEDA |
Win98 VC++6.0 LEDA3.8 |
| 幾何グラフ（交グラフ）、区間グラフ | ||||
| 直並列グラフ | ||||
| 辺彩色アルゴリズム | 彦田 卓史 （東北大学） |
実行形式 | MS-Win Visual C++ LEDA |
Win98 VC++6.0 LEDA3.8 |
| フローチャートグラフ、ブロックダイアグラム | ||||
| 構文解析・編集アルゴリズム | ||||
| 2部グラフ、有向グラフ | ||||
| 制限された２部グラフの 最大マッチングアルゴリズム |
浅野 孝夫 （中央大学） |
|||
| 有向グラフの被覆アルゴリズム | ||||
| Perfect graph | ||||
| 木 | ||||
| 配置アルゴリズム | ||||
| その他 | ||||
| 最長非減少部分列問題 | ||||
| 極大要素問題 | ||||
| アルゴリズム | 提供者 | 提供形態 | 必要環境 | 動作確認 |
|---|---|---|---|---|
| 地理情報処理 | ||||
| デマンドバスのスケジューリングアルゴリズム | ||||
| (時間枠付きの問題を解くメタヒューリスティックアルゴリズム) | ||||
| 画像処理 | ||||
| 距離変換及びモルフォロジー演算デモ | 櫻井 敦史 （名古屋大学） |
実行形式 | Win95/98/NT4.0 (Mfc42d.dll,Msvcrtd.dllが必要) |
|
| 精度保証近似アルゴリズム | ||||
| 配送計画、施設配置に対する近似アルゴリズム | ||||
| スタイナーネットワーク、高信頼ネットワーク Rao, Goemans-Williamson | ||||
| スケジューリング | ||||
| 集合被覆 | ||||
| Knapsack, Binpacking | ||||
| MAX CUT, MAX SAT, CSP | ||||
| TSP | ||||
| Multicut, Multicommodity flow | ||||
| Feedback vertex set | ||||