目次
序文
第 1 章 はじめに:いくつかの代表的問題
1.1 安定マッチング
1.2 五つの代表的な問題
問題 1.2 区間スケジューリング Interval Scheduling
問題 1.3 重み付き区間スケジューリング Weighted Interval Scheduling
問題 1.4 二部グラフのマッチング Bipartite Matiching
問題 1.5 独立集合 Independent Set
問題 1.6 競争的施設配置 Competitive Facility Location
ノートと発展文献
Gale, Shapley(1962),Gale (2001),Gusfield, Irving(1989) Kunuth(1997c) →安定マッチング
第 2 章 アルゴリズム解析の基礎事項
2.1 計算容易性
2.2 増加の漸近的オーダー
2.3 リストと配列による安定マッチングアルゴリズムの実装
2.4 よく現れる計算時間の復習
2.5 より複雑なデータ構造：優先順位付きキュー
ノートと発展文献
Cobham, Rabin, Edmonds, Hartmanis, Stearns の多項式時間での可解性研究→Sipser(1992)の論文あり
Tarjanの講演(1987)漸近的オーダーの概念→Knuth(1997a)
Willams(1964), Floyd(1964)優先順位付きキュー
Tarjan(1983)データ構造
Mehlhorn, Naher(1999)LEDA(Library of Efficient Datatypes and Algorithms)アルゴリズムライブラリ
第 3 章 グラフ
3.1 基本的定義と応用
3.2 グラフの連結性とグラフ走査
3.3 キューとスタックを用いたグラフ走査
3.4 二部グラフ性の判定：幅優先探索の応用
3.5 有向グラフの連結性
3.6 有向無閉路グラフとトポロジカル順序付け
ノートと発展文献
Euler(1736)がグラフ理論の起源
Berge(1976), Bollobas(1998), Diestel(2000)のよる本がまとまっている
Barabashi(2002), Watts(2002)の本は、物理、社会におけるグラフへの応用がまとまっている
Tarjan(1983)はグラフ走査アルゴリズムがまとまっている
第 4 章 グリーディアルゴリズム
貪欲さはうまく機能するか？を問う
4.1 区間スケジューリング：グリーディアルゴリズムの先進性
4.2 遅延最小化スケジューリング：交換議論
4.3 最適キャッシング：より複雑な交換議論
第 5 章 分割統治法
第 6 章 動的計画法
第 7 章 ネットワークフロー
第 8 章 NPと計算困難性
第 9 章 PSPACE:クラスNPを超える問題のクラス
第10章 計算容易性の拡大
第11章 近似アルゴリズム
第12章 局所探索
第13章 乱択アルゴリズム
第14章 永遠に動作するアルゴリズム
問題の一覧
アルゴリズム一覧
1.1安定マッチングアルゴリズム
3.1二部グラフ性判定アルゴリズム
3.2トポロジカルソート
序文
第 1 章 はじめに:いくつかの代表的問題
1.1 安定マッチング
1.2 五つの代表的な問題
問題 1.2 区間スケジューリング Interval Scheduling
問題 1.3 重み付き区間スケジューリング Weighted Interval Scheduling
問題 1.4 二部グラフのマッチング Bipartite Matiching
問題 1.5 独立集合 Independent Set
問題 1.6 競争的施設配置 Competitive Facility Location
ノートと発展文献
Gale, Shapley(1962),Gale (2001),Gusfield, Irving(1989) Kunuth(1997c) →安定マッチング
第 2 章 アルゴリズム解析の基礎事項
2.1 計算容易性
2.2 増加の漸近的オーダー
2.3 リストと配列による安定マッチングアルゴリズムの実装
2.4 よく現れる計算時間の復習
2.5 より複雑なデータ構造：優先順位付きキュー
ノートと発展文献
Cobham, Rabin, Edmonds, Hartmanis, Stearns の多項式時間での可解性研究→Sipser(1992)の論文あり
Tarjanの講演(1987)漸近的オーダーの概念→Knuth(1997a)
Willams(1964), Floyd(1964)優先順位付きキュー
Tarjan(1983)データ構造
Mehlhorn, Naher(1999)LEDA(Library of Efficient Datatypes and Algorithms)アルゴリズムライブラリ
第 3 章 グラフ
3.1 基本的定義と応用
3.2 グラフの連結性とグラフ走査
3.3 キューとスタックを用いたグラフ走査
3.4 二部グラフ性の判定：幅優先探索の応用
3.5 有向グラフの連結性
3.6 有向無閉路グラフとトポロジカル順序付け
ノートと発展文献
Euler(1736)がグラフ理論の起源
Berge(1976), Bollobas(1998), Diestel(2000)のよる本がまとまっている
Barabashi(2002), Watts(2002)の本は、物理、社会におけるグラフへの応用がまとまっている
Tarjan(1983)はグラフ走査アルゴリズムがまとまっている
第 4 章 グリーディアルゴリズム
貪欲さはうまく機能するか？を問う
4.1 区間スケジューリング：グリーディアルゴリズムの先進性
4.2 遅延最小化スケジューリング：交換議論
4.3 最適キャッシング：より複雑な交換議論
第 5 章 分割統治法
第 6 章 動的計画法
第 7 章 ネットワークフロー
第 8 章 NPと計算困難性
第 9 章 PSPACE:クラスNPを超える問題のクラス
第10章 計算容易性の拡大
第11章 近似アルゴリズム
第12章 局所探索
第13章 乱択アルゴリズム
第14章 永遠に動作するアルゴリズム
問題の一覧
アルゴリズム一覧
1.1安定マッチングアルゴリズム
3.1二部グラフ性判定アルゴリズム
3.2トポロジカルソート
タグ
コメントをかく