**1. Single-source shortest paths** (directed (simpler for undirected), weighted)

NB. single-pair shortest path is as hard as SSSP.

a. Dijkstra’s algorithm (O(|V|log|V|+|E|), O((|V|+|E|)·log|V|) if common heap), works only for non-negative weighted graphs.

b. Bellman-Ford (O(|V|·|E|)), can handle graphs with negative weighted edges (such case will be reported), works even for graphs with negative cycles.

Special case: DAG, O(|V|+|E|), can handle graphs with negative weighted edges.

**2. All-pair shorted paths**

a. Dynamic-programming algorithm O(|V|^3 ·log|V|)

b. Ford-Warshall algorithm O(|V|^3)

c. Johnson’s algorithm (O(|V|^2 ·log|V|+|V|·|E| )), changes the edge weights so that Dijkstra’s algorithm can be used.

NB1. Graph modification (a useful idea).

NB2. all above algorithms can not handle graphs with negative cycles.

**3. Maximum flow**

a. Ford-Fulkerson method, based on Max-flow min-cut Theorem.

number of iterations in Edmonds-Karp is O(|V|·|E|), therefore, the running time is O(|V|·|E|^2)

Applications:

1). Edge(vertex) disjoint path problem

2). Maximum matching in bipartite graphs

3). Capacity limitation for vertices

4). Point-to-rectangle problem

5). Edge(vertex) connectivity number problem (directed and undirected versions). This connectivity number problem of undirected graph can be solved by solving the edge disjoint-path problem O(|V|-1) times.

**4. NP-Complete problems:**

1). Clique

2). Vertex cover

3). Hamiltonian Cycle

4). TSP

5). Minimal vertex(edge) disjoint *cycle covers*

Minimum-Weight *Cycle Cover* Problem (MWCCP)

NB1. the proof of NP-hardness can be proceed by following the reduction path: 1->2->3->4.

NB2. approximation algorithms exists for vertex cover, and TSP if certain conditions are satisfied.

**5. Bisimulation**

**6. Modular decomposition**

a. Incremental method, O(|V|^2)

b. Linear complexity O(|V|+|E|), proposed in 2005.

—————————————————————————

Above are the graph related problems I met and studied so far. To know more about them if you are interested, you may refer to the book* Introduction to algorithms* by T.H.Cormen* et al*. Also, the slides given by Dr. Mark de Berg is quite helpful, which can be found here: http://www.win.tue.nl/~mdberg/Onderwijs/Algoritmiek_2012/2IL15.htm.