Posts Tagged ‘Graph’

Graph problem list

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.

Advertisements

Read Full Post »