## Saturday, 18 June 2011

### Graphs

• 3D Surface Tracker Technology. Process to add images on walls in a video while hidden surfaces are taken into account.
• Bellman-Ford. Computes shortest paths in a weighted graph (where some of the edge weights may be negative).
• Dijkstra's algorithm. Computes shortest paths in a graph with non-negative edge weights.
• Perturbation methods. An algorithm that computes a locally shortest paths in a graph.
• Floyd-Warshall. Solves the all pairs shortest path problem in a weighted, directed graph.
• Floyd's cycle-finding. Finds cycles in iterations.
• Johnson. All pairs shortest path algorithm in sparse weighted directed graph.
• Kruskal. Finds a minimum spanning tree for a graph.
• Prim's. Finds a minimum spanning tree for a graph. Also called DJP , Jarník or Prim–Jarník algorithm.
• Boruvka. Finds a minimum spanning tree for a graph.
• Ford-Fulkerson. Computes the maximum flow in a graph.
• Edmonds-Karp. Implementation of Ford-Fulkerson.
• Nonblocking Minimal Spanning Switch. For a telephone exchange.
• Woodhouse-Sharp. Finds a minimum spanning tree for a graph.
• Spring based. Algorithm for graph drawing.
• Hungarian. Algorithm for finding a perfect matching.
• Coloring algorithm. Graph coloring algorithm.
• Nearest neighbour. Find nearest neighbour.
• Topological sort. Sort a directed acyclic graph in such a manner that each node comes before all nodes to which it has edges (according to directions).
• Tarjan's off-line least common ancestors algorithm. Compute lowest common ancestors for pairs of nodes in a tree.