Louis Perrochon. Abteilung für Informatik, ETH Zürich. March 1992.

Keywords: graph theory, transitive orientation

Language: German

Abstract:

Die vorliegende Arbeit befasst sich mit Algorithmen, die gerichtete Graphen auf Transitivität testen. Insbesondere wird ein effizientes Verfahren für die bei der transitiven Orientierung ungerichteter Graphen durch den Algorithmus von Spinrad entstehenden Graphen vorgestellt.

Ways to test if directed graphs are transitive are implemented and benchmarked. In particular an efficient algorithm for the test of the graphs produced by the algortithm of Spinrad for transitive orientation of undirected graphs is developped.

Available files: [gzipped Postscript]