Property testing in gradbeschränkten gerichteten Graphen unter Nichtsichtbarkeit eingehender Kanten

Abstract

Diese Arbeit untersucht Property-Testing in gerichteten gradbeschränkten Graphen. Property-Testing ist eine Technik zum Lösen von Entscheidungsproblemen, wobei durch Relaxierung des Problems und Verwendung von Randomisierung eine sublineare Laufzeit angestrebt wird. Gradbeschränkte Graphen sind das übliche Modell, um Property-Testing in dünn besetzten Graphen zu untersuchen; hierbei wird angenommen, dass der Eingabegraph in Adjazenzlistendarstellung vorliegt und die Länge der Adjazenzlisten durch eine Konstante D beschränkt ist. Im Rahmen dieser Arbeit gehen wir davon aus, dass in gerichteten Graphen jeweils nur die ausgehenden Kanten in den Adjazenzlisten enthalten sind. Die dadurch deutlich eingeschränkten Möglichkeiten der Graphexplorierung führen dazu, dass Probleme im Vergleich zu ihren Pendants in ungerichteten Graphen deutlich schwieriger zu lösen sind; dies konnten Bender und Ron in 2002 zum Beispiel für starken Zusammenhang zeigen. In dieser Arbeit werden Property-Testing-Algorithmen im oben genannten Modell für drei Probleme vorgestellt: Starker Zusammenhang, Subgraphfreiheit mit dem Spezialfall 3-Stern-Freiheit und die Spanner-Eigenschaft in geometrischen gerichteten Graphen.