Katharina Klost

Complexity of recognizing generalized transmission graphs

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Master of Science (M.Sc.)
Abgabedatum: 16.03.2017
Homepage des Autors:

Kurzbeschreibung

Der allgemeine Transmissionsgraph einer Menge von geometrischen Objekten, mit einem ausgezeichneten  Punkt für jedes Element der Menge, hat einen Knoten pro Element und eine gerichtete Kante (u,v) genau dann wenn der Punkt von v in u liegt. Diese Graphen sind ein mögliches Modell für Erreichbarkeit von Antennen.

Die Komplexitätsklasse ETR enthält alle Sprachen, die in Polynomialzeit auf einen Satz der Form ∃x_1,.,x_n:ϕ(x_1,..., x_n) reduziert werden können. Hierbei stammen x_1,..., x_n aus den reelen Zahlen. Es ist
bekannt, dass ETR zwischen NP und PSPACE liegt.

Für viele geometrische Entscheidungsprobleme, wie zum Beispiel das Erkennen von Kreisgraphen und  Schnittgraphen von Strecken ist bekannt, dass diese ETR-vollständig sind.

In dieser Arbeit werden allgemeine Transmissionsgraphen formal definiert und es wird gezeigt, dass das Erkennen von allgemeinen Transmissionsgraphen von k-Kugeln, regelmäßigen Polygonen, Strecken und Kreissektoren ETR-vollständig ist.