アルゴリズム

アルゴリズム設計マニュアル 下

S. S. スキーナ

丸善出版

第II部 ヒッチハイカーのためのアルゴリズム案内

第11章 アルゴリズム問題のカタログ

第12章 データ構造

  • 12.1 辞書
  • 12.2 優先順位付きキュー
  • 12.3 サフィックス木とサフィックス配列
  • 12.4 グラフのデータ構造
  • 12.5 集合のデータ構造
  • 12.6 kd木

第13章 数値問題

  • 13.1 線形連立方程式を解く
  • 13.2 帯幅の削減
  • 13.3 行列の乗算
  • 13.4 行列式とパーマネント
  • 13.5 制約付き最適化と制約なし最適化
  • 13.6 線形計画法
  • 13.7 乱数の生成
  • 13.8 因数分解と素数判定
  • 13.9 任意精度の算術演算
  • 13.10 ナップザック問題
  • 13.11 離散フーリエ変換

第14章 組合せ問題

  • 14.1 ソート
  • 14.2 探索
  • 14.3 中央値と選択
  • 14.4 順列の生成
  • 14.5 部分集合の生成
  • 14.6 分割の生成
  • 14.7 グラフの生成
  • 14.8 カレンダーの計算
  • 14.9 ジョブスケジューリング
  • 14.10 充足可能性

第15章 グラフ問題:多項式時間

  • 15.1 連結成分
  • 15.2 位相的ソート
  • 15.3 最小スパニング木
  • 15.4 最短経路
  • 15.5 推移的閉包と推移的簡約
  • 15.6 マッチング
  • 15.7 オイラー閉路/中国人郵便配達
  • 15.8 辺連結度と点連結度
  • 15.9 ネットワークフロー
  • 15.10 グラフをうまく描く
  • 15.11 木を描画する
  • 15.12 平面性の判定と埋め込み

第16章 グラフ問題:困難な問題

  • 16.1 クリーク
  • 16.2 独立集合
  • 16.3 頂点被覆
  • 16.4 巡回セールスマン
  • 16.5 ハミルトン閉路
  • 16.6 グラフ分割
  • 16.7 頂点彩色
  • 16.8 辺彩色
  • 16.9 グラフ同型
  • 16.10 シュタイナー木
  • 16.11 帰還辺/帰還点集合

第17章 計算幾何学

  • 17.1 頑健な幾何的基本計算
  • 17.2 凸包
  • 17.3 三角分割
  • 17.4 ボロノイ図
  • 17.5 最近接点探索
  • 17.6 領域探索
  • 17.7 点位置決定
  • 17.8 交差検出
  • 17.9 ビンパッキング
  • 17.10 中心軸変換
  • 17.11 多角形分割
  • 17.12 多角形の簡約化
  • 17.13 形の類似性
  • 17.14 動作計画
  • 17.15 直線アレンジメントの管理
  • 17.16 ミンコフスキー和

第18章 集合と文字列の問題

  • 18.1 集合被覆
  • 18.2 集合パッキング
  • 18.3 文字列マッチング
  • 18.4 近似文字列マッチング
  • 18.5 テキスト圧縮
  • 18.6 暗号
  • 18.7 有限状態機械の最小化
  • 18.8 最長共通部分文字列/部分列
  • 18.9 最短共通超文字列

第19章 アルゴリズム資源

  • 19.1 ソフトウェアシステム
    • 19.1.1 LEDA
    • 19.1.2 CGAL
    • 19.1.3 Boost Graph Library
    • 19.1.4 GOBLIN
    • 19.1.5 Netlib
    • 19.1.6 Collected Algorithm of the ACM
    • 19.1.7 SourceForgeとCPAN
    • 19.1.8 The Stanford GraphBase
    • 19.1.9 Combinatorica
    • 19.1.10 本からのプログラム
  • 19.2 データ資源
  • 19.3 オンライン参考文献
  • 19.4 プロによる相談サービス

参考文献
訳者後書き
索引