Authors: Hellweg, Frank
Title: Property testing in gradbeschränkten gerichteten Graphen unter Nichtsichtbarkeit eingehender Kanten
Language (ISO): de
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.
Subject Headings: Algorithmen
Graphalgorithmen
Property testing
Randomisierte Algorithmen
Sublinearzeitalgorithmen
Theoretische Informatik
URI: http://hdl.handle.net/2003/31249
http://dx.doi.org/10.17877/DE290R-13142
Issue Date: 2013-12-06
Appears in Collections:LS 02 Komplexitätstheorie und Effiziente Algorithmen
Sublinear Algorithms for the Analysis of Very Large Graphs

Files in This Item:
File Description SizeFormat 
Dissertation.pdfDNB1.21 MBAdobe PDFView/Open


This item is protected by original copyright



All resources in the repository are protected by copyright.