Gabow's algorithm

Gabow's algorithm

In graph theory, the Cheriyan/Mehlhorn/Gabow algorithm is a linear-time method for finding strong components of a digraph. It was discovered in 1996 by J. Cheriyan and K. Mehlhorn and rediscovered in 1999 by H. Gabow and is a variation on Tarjan's algorithm. The algorithm uses a second stack to decide when to remove vertices in the same strong component from the main stack, instead of a vertex-indexed array of preorder numbers.

References

* Robert Sedgewick. "Algorithms in C", Third Edition, Part 5 - Graph Algorithms. Addison-Wesley, 2002. ISBN 0-201-31663-3. Section 19.8, pp.205

* J. Cheriyan and K. Mehlhorn. "Algorithms for dense graphs and networks on the random access computer", Algorithmica, volume 15, pp. 521-549, 1996.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Kosaraju's algorithm — In computer science, Kosaraju s algorithm is an algorithm to find the strongly connected components of a directed graph. Aho, Hopcroft and Ullman credit it to an unpublished paper from 1978 by S. Rao Kosaraju. It makes use of the fact that the… …   Wikipedia

  • Tarjan's strongly connected components algorithm — Tarjan s Algorithm (named for its discoverer, Robert Tarjan) is a graph theory algorithm for finding the strongly connected components of a graph. It can be seen as an improved version of Kosaraju s algorithm, and is comparable in efficiency to… …   Wikipedia

  • Coffman–Graham algorithm — In job shop scheduling and graph drawing, the Coffman–Graham algorithm is an algorithm, named after Edward G. Coffman, Jr. and Ronald Graham, for arranging the elements of a partially ordered set into a sequence of levels. The algorithm chooses… …   Wikipedia

  • Tarjan's off-line least common ancestors algorithm — In computer science, Tarjan s off line least common ancestors algorithm is an algorithm for computing lowest common ancestors for pairs of nodes in a tree, based on the union find data structure. The least common ancestor of two nodes d and e in… …   Wikipedia

  • 2-satisfiability — In computer science, 2 satisfiability (abbreviated as 2 SAT or just 2SAT) is the problem of determining whether a collection of two valued (Boolean or binary) variables with constraints on pairs of variables can be assigned values satisfying all… …   Wikipedia

  • Shortest path problem — A graph with 6 vertices and 7 edges In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. An example is… …   Wikipedia

  • Strongly connected component — Graph with strongly connected components marked A directed graph is called strongly connected if there is a path from each vertex in the graph to every other vertex. In particular, this means paths in each direction; a path from a to b and also a …   Wikipedia

  • List of mathematics articles (G) — NOTOC G G₂ G delta space G networks Gδ set G structure G test G127 G2 manifold G2 structure Gabor atom Gabor filter Gabor transform Gabor Wigner transform Gabow s algorithm Gabriel graph Gabriel s Horn Gain graph Gain group Galerkin method… …   Wikipedia

  • Edge coloring — A 3 edge coloring of the Desargues graph. In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge… …   Wikipedia

  • Pseudoforest — A 1 forest (a maximal pseudoforest), formed by three 1 trees In graph theory, a pseudoforest is an undirected graph[1] in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of ve …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”