Springe direkt zu Inhalt

Konrad Pflüger:

Ein Algorithmus zur Erreichbarkeit in planaren gerichteten azyklischen Graphen mit O(log n) Platz

Kurzbeschreibung

Das Erreichbarkeitsproblem auf Graphen ist ein fundamentales Problem für die Speicherkomplexitätstheorie, da Erreichbarkeit in ungerichteten Graphen in L liegt, während Erreichbarkeit in gerichteten Graphen vollständig für NL ist. Diese Arbeit befasst sich mit dem Algorithmus von Stolee et. al. zur Erreichbarkeit in planaren DAGs mit O(log n) Quellen, der die Klasse der gerichteten Graphen, für die Erreichbarkeit in L liegt, erweitert. Sie bauen dabei auf dem Algorithmus von Allender et. al. zur Erreichbarkeit in planaren DAGs mit genau einer Quelle auf. In dieser Arbeit werden zunächst die Komplexitätsklassen L und NL definiert und eine formale Definition von planaren Graphen angegeben. Danach wird der Algorithmus von Stolee et. al. vorgestellt, wobei die Konzepte aus dem Algorithmus von Allender et. al. auf planare DAGs mit mehreren Quellen übertragen werden. Anschließend wird noch gezeigt, wie man in L auf gerichtete Zyklen testen kann.

Abschluss
Bachelor of Science (B.Sc.)
Abgabedatum
07.05.2026