[Mittagsseminar TI] Fwd: [i-prof] Einladung zur Verteidigung meiner Masterarbeit

[Wolfgang Mulzer <mulzer@inf.fu-berlin.de>]

-------- Forwarded Message --------
Subject: 	[i-prof] Einladung zur Verteidigung meiner Masterarbeit
Date: 	Tue, 14 Mar 2017 16:03:13 +0100
From: 	Katharina Klost <kathklost@zedat.fu-berlin.de>
To: 	i-profs@inf.fu-berlin.de, i-wimis@inf.fu-berlin.de,
i-studi@inf.fu-berlin.de
CC: 	renee.zentiks@fu-berlin.de



Sehr geehrte Damen und Herren,

hiermit lade ich Sie herzlich zur Verteidigung meiner Masterarbeit mit
dem Titel "Complexity of recognizing generalized transmission graphs" ein.

Die Präsentation findet am Donnerstag, den 16.03.2017 um 12:00 s.t. im
Rahmen des Mittagssemiars für Theoretische Informatik in SR 055 statt.
Die Arbeit wurde von Prof. Dr. Wolfgang Mulzer betreut, Zweitkorrektor
ist PD Dr. Klaus Kriegel

Mit freundlichen Grüßen

Katharina Klost


*Zusammenfassung:*
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.

*Abstract:*
Given an arrangement of geometric objects with one point of each object
singled out. The generalized transmission graph of this arrangement
consists of one vertex per element and a directed edge /(u,v)/ if and
only if the point of /v/ lies in /u/.
These graphs can serve as a generalized model of antenna reachability.

The complexity class ETR contains all problems that are polynomial time
reducible to a sentence of the form /∃x_1,.,x_n:ϕ(x_1,..., x_n)/ where
/x_1,..., x_n/ are interpreted over the real numbers. It aims to capture
the complexity of the existential theory of the reals. It is well known
that ETR lies between NP and PSPACE.

For many geometric decision problems, such as recognition of disk graphs
and of intersection graphs of lines, it is known that they are complete
for ETR.

In this thesis we formally introduce the class of /generalized
transmission graphs/ and show that the recognition problem of
generalized transmission graphs of k-spheres, regular polygons, line
segments and circular sectors is complete for the complexity class ETR.



_______________________________________________
Automatischer Mailverteiler an Gruppe 'ml-i-prof-mi'.
Hinweise dazu siehe Hilfeseite:
https://www.mi.fu-berlin.de/w/Tec/AnkuendigungsVerteiler

Attachment: smime.p7s
Description: S/MIME Cryptographic Signature