Property testing in gradbeschränkten gerichteten Graphen unter Nichtsichtbarkeit eingehender Kanten
Loading...
Date
2013-12-06
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Table of contents
Keywords
Algorithmen, Graphalgorithmen, Property testing, Randomisierte Algorithmen, Sublinearzeitalgorithmen, Theoretische Informatik