Publications by Louis Perrochon
Site Areas
Introduction
Publications
  By Area
  By Class
DanceSport
Photography

 

Books
School Goes Internet
Bool'sche Matrixmultiplikationen und verwandte Probleme

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]

Copyright Louis Perrochon. All Rights reserved.