[Mittagsseminar TI] Mittagsseminar am 12.09. u. 13.09.2016

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

Im Rahmen des Mittagsseminars der
Theoretischen Informatik der FU Berlin
spricht am

   Montag, 12.09.2016 (SR 053)
   Max Willert
   zum Thema:
     Routing Schemes for Polygonal Domains

und am

   Dienstag, 13.09.2016 (SR 055)
   Henning Hinze, Universität Rostock
   zum Thema:
     The lattice of subclasses of P_k of quasilinear functions

***************************************************
Uhrzeit: 12 Uhr s.t.
***************************************************

Abstract Willert:
Routing in networks is a fundamental problem that occurred in the 1980's
and was well studied since then. However, there are still open problems,
which have not been solved until now. In this talk I propose routing
schemes for special graph classes. Let $G=(V,E)$ be a weighted network 
or graph. For any two nodes $p,q\in V$ I would like to be able to route 
a data package from $p$ to $q$. A routing scheme $\Rr$ assigns to each 
node $p\in V$ a \textit{label} $l(p)\in\{0,1\}^*$ and a \textit{routing 
table} $\rho(p)\in\{0,1\}^*$. The label identifies the node in the 
network and the routing table is its own local \textit{read-only} 
memory. Now the scheme works in the following way: the scheme starts 
with a \textit{current node} $p$, the label of a \textit{target node} 
and some additional information in the data package, called 
\textit{header}. As a next step, the scheme computes a new node in
the network, where the data package is forwarded to. It can use the
information in the header and the local memory. The resulting sequence 
of nodes is the \textit{routing path}. The stretch of $\Rr$ is the 
maximum ratio of the Euclidean length of the routing path and the 
shortest path. Travelling in polygons is a well-known problem. The 
\textit{visibility graph} $\VG(P)$ of a polygon $P$ with $n$ vertices 
and $h$ holes is a graph in which two vertices in $P$ are connected, iff 
they can see each other, meaning that the line segment between the two 
vertices is contained in $P$. I present the first routing scheme for 
polygons with holes. For any $\epsilon>0$ the routing scheme provides 
the stretch $1+\epsilon$ and uses no additional information in the 
header of a data package. The labels have $\Oe(\log n)$ bits and the 
corresponding routing tables are of size $\Oe(\epsilon^{-1}h\log n)$. 
The preprocessing time is $\Oe(n^3+nh\epsilon^{-1})$ and can be improved 
for simple polygons to $\Oe(n^2+n\epsilon^{-1})$.

===============================
Abstract Hinze:
The talk will summarize the results achieved in my master thesis. The 
thesis is located in the area of multi-valued logic and function 
algebras which is a branch of discrete mathematics and mathematical 
logic and in particular deals with so called quasilinear functions. Here 
I extended some known facts of the 3-valued logic to the 4-valued logic 
and found a new class of functions not existing in the 3-valued logic 
and was able to apply the known facts as well as characterize these 
classes. I will give quick overview of the basics of the theory and will 
then lead to the results gathered.

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