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

Hellweg, Frank

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

dc.contributor.advisor	Sohler, Christian
dc.contributor.author	Hellweg, Frank
dc.contributor.referee	Westermann, Matthias
dc.date.accepted	2013-11-14
dc.date.accessioned	2013-12-06T08:10:47Z
dc.date.available	2013-12-06T08:10:47Z
dc.date.issued	2013-12-06
dc.description.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.	de
dc.identifier.uri	http://hdl.handle.net/2003/31249
dc.identifier.uri	http://dx.doi.org/10.17877/DE290R-13142
dc.language.iso	de	de
dc.subject	Algorithmen	de
dc.subject	Graphalgorithmen	de
dc.subject	Property testing	de
dc.subject	Randomisierte Algorithmen	de
dc.subject	Sublinearzeitalgorithmen	de
dc.subject	Theoretische Informatik	de
dc.subject.ddc	004
dc.title	Property testing in gradbeschränkten gerichteten Graphen unter Nichtsichtbarkeit eingehender Kanten	de
dc.type	Text	de
dc.type.publicationtype	doctoralThesis	de
dcterms.accessRights	open access

Files

Original bundle

Now showing 1 - 1 of 1

Name:: Dissertation.pdf
Size:: 1.18 MB
Format:: Adobe Portable Document Format
Description:: DNB

Download

License bundle

Now showing 1 - 1 of 1

Name:: license.txt
Size:: 1.85 KB
Format:: Item-specific license agreed upon to submission
Description:

Download

Collections

LS 02 Komplexitätstheorie und Effiziente Algorithmen
Sublinear Algorithms for the Analysis of Very Large Graphs