# Graph Algorithms
## Introduction

* Königsberg problem
* Graph theory
* Glossary of graph theory terms
* Undirected graph
* Directed graph
* Directed acyclic graphs (DAG)

### Graph Representations and Data Structures

* Graph (abstract data type)
* Adjacency list
* Adjacency matrix
* Incidence matrix
* Implicit graph

## Graph Exploration and Vertex Ordering

* Depth-first search (DFS)
* Breadth-first search (BFS)
* Lexicographic breadth-first search
* Iterative deepening depth-first search
* Topological sorting
* Application: Dependency Graphs

## Connectivity of Undirected Graphs

* Connected components
* Edge connectivity
* Vertex connectivity
* Menger's theorems on edge and vertex connectivity
* Ear decomposition
* Algorithms for 2-edge-connected components
* Algorithms for 2-vertex-connected components
* Algorithms for 3-vertex-connected components
* Karger's algorithm

## Connectivity of Directed Graphs

* Strongly connected components
* Tarjan's strongly connected components algorithm
* Path-based strong component algorithm
* Kosaraju's strongly connected components algorithm
* Reachability
* Transitive closure
* Transitive reduction
* Application: 2-satisfiability (2-SAT)

## Planar Graphs and Graph Drawing
### Planar Graphs

* Planar graph
* Dual graph
* Fáry's theorem
* Steinitz's theorem
* Planarity testing
* Left-right planarity test

### Graph Drawing

* Graph drawing
* Force-directed graph drawing
* Layered graph drawing
* Upward planar drawing
* Graph embedding
* Sociogram
* Concept map

## Shortest Paths

* Shortest path problem
* Dijkstra's algorithm for single-source shortest paths with positive edge lengths
* Bellman–Ford algorithm for single-source shortest paths allowing negative edge lengths
* Johnson's algorithm for all-pairs shortest paths in sparse graphs
* Floyd–Warshall algorithm for all-pairs shortest paths in dense graphs
* Suurballe's algorithm for two shortest disjoint paths
* Bidirectional search
* A* search algorithm
* Longest path problem
* Widest path problem
* Canadian traveller problem
* K shortest path routing
* Application: Centrality analysis of social networks
* Application: Schulze voting system

## Minimum Spanning Trees

* Minimum spanning tree
* Borůvka's algorithm
* Kruskal's algorithm
* Prim's algorithm
* Edmonds's algorithm for directed minimum spanning trees
* Degree-constrained spanning tree
* Maximum-leaf spanning tree
* K-minimum spanning tree
* Capacitated minimum spanning tree
* Application: Single-linkage clustering
* Application: Maze generation

## Cliques, Independent Sets, and Coloring

* Clique problem
* Bron–Kerbosch algorithm for listing all maximal cliques
* Independent set problem
* Maximal independent set
* Graph coloring
* Bipartite graph
* Greedy coloring
* Ramsey's theorem
* Application: Register allocation

## Covering and Domination

* Vertex cover
* Dominating set
* Feedback vertex set
* Feedback arc set

## Tours

* Eulerian path
* Hamiltonian path
* Hamiltonian path problem
* Travelling salesman problem
* Bottleneck traveling salesman problem
* Christofides' heuristic for the TSP
* Route inspection problem

## Matching

* Matching
* Hopcroft–Karp algorithm for maximum matching in bipartite graphs
* Edmonds's algorithm for maximum matching in non-bipartite graphs
* Assignment problem
* Hungarian algorithm for the assignment problem
* FKT algorithm for counting matchings in planar graphs
* Stable marriage problem
* Stable roommates problem
* Permanent
* Computing the permanent

## Network Flow

* Maximum flow problem
* Max-flow min-cut theorem
* Ford–Fulkerson algorithm for maximum flows
* Edmonds–Karp algorithm for maximum flows
* Dinic's algorithm for maximum flows
* Push–relabel maximum flow algorithm
* Closure problem
* Minimum-cost flow problem

## Special Classes of Graphs

* Interval graph
* Chordal graph
* Perfect graph
* Intersection graph
* Unit disk graph
* Line graph
* Claw-free graph
* Median graph

## Graph Isomorphism

* Graph isomorphism
* Graph isomorphism problem
* Graph canonization
* Subgraph isomorphism problem
* Color-coding
* Induced subgraph isomorphism problem
* Maximum common induced subgraph
* Maximum common edge subgraph

## Graph Decomposition and Graph Minors

* Graph partition
* Kernighan–Lin algorithm
* Tree decomposition
* Branch-decomposition
* Path decomposition
* Planar separator theorem
* Graph minor
* Courcelle's theorem
* Robertson–Seymour theorem
* Bidimensionality