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.

0 comments:

Post a comment