(01CB221)

Class plan of the first half

1. Graph 　グラフ

   Keywords: graph, network, path , cycle, cut, subgraph, tree, bipartite graph, planar graph, incidence matrix, adjacency matrix, adjacency list

2. Graph Search グラフ探索

   Keywords: depth-first search(DFS), topological order, strongly connected component decomposition, breadth-first-search(BFS)

3. Algorithms and Complexity　アルゴリズムと複雑性

   Keywords: problem and instance, Turing machine, RAM, computability, time complexity, space complexity, size of problem, asymptotic bounds, worst case analysis, average case analysis, polynomial time algorithm, strongly polynomial time algorithm, pseudo polynomial time algorithm, exponential time algorithm, class P, class NP, class NP-complete, SAT, QLIQE, VERTEX-COVER, SUBSET-SUM, HAMILTONIAN CYCLE, PARTITION, 3DIMENSIONAL MACHING, INDEPENDENT-SET, polynomial-time reduction, class NP-hard, class co-NP, class PSPACE

4. Spanning Tree　全域木

   Keywords: fundamental cycle/cut, Prim method, Kruskal method, minimum arborescence, spanning tree on planar graph, MST-polytope, primal-dual algorithm

5. Maximum Flow 最大流

   Keywords: maximum-flow minimum-cut theorem, augmenting path method, residual network, LP, preflow-push method,

6. Minimum Cost Flow 最小費用流

   Keywords: minimum circulation problem, negative-cycle canceling algorithm, positive-cut canceling algorithm, successive shortest path algorithm, primal-dual algorithm, scaling algorithm

References

• 繁野麻衣子「ネットワーク最適化とアルゴリズム」朝倉書店(2010)
• W. Hochstattler and A. Schliep, An Intertactive Course in Combinatorial Optimization, Springer (2010)
• J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley (2006)
• B. Korte and J. Vygen, Combinatorial Optimization, Springer (2000)

return 戻る