ISSN:
1436-5057
Keywords:
68 E 10
;
Digraphs
;
strongly connected components
;
transitive closure
;
transitive reduction
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Zusammenfassung Verschiedene effiziente Transitive-Hülle-Algorithmen arbeiten auf den stark zusammenhängenden Komponenten eines gerichteten Graphen; einige davon verwenden den Algorithmus von Tarjan [17]. Wir nützen Sachverhalte aus der Graphentheorie und die speziellen Eigenschaften von Tarjans Algorithmus aus, um einen neuen, verbesserten Algorithmus zu entwickeln. Die transitive Reduktion eines gerichteten Graphen, wie sie in [1] definiert wird, läßt sich als Nebenprodukt bestimmen.
Notes:
Abstract Several efficient transitive closure algorithms operate on the strongly connected components of a digraph, some of them using Tarjan's algorithm [17]. Exploiting facts from graph theory and the special properties of Tarjan's algorithm we develop a new, improved algorithm. The transitive reduction of a digraph defined in [1] may be obtained as a byproduct.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02242140
Permalink
