Linear-Zeit Transitive Orientierung von Vergleichbarkeitsgraphen
In der Arbeit https://www.cs.colostate.edu/~rmm/linModDecomp.pdf wird beschrieben, wie Graphen einer bestimmten Graphenklasse in Linearzeit in Module zerlegt werden können. Diese Module können dazu genutzt werden, diesen Graphen, ebenfalls in Linearzeit, transitiv zu orientieren. In der Projektarbeit erklären und beweisen Sie den daraus entstehenden Algorithmus mithilfe von weiteren, selbst ausgewählten Veröffentlichungen.
Informationen: Dominik Dürrschnabel