\documentstyle[12pt,german]{article}
\addtolength{\oddsidemargin}{-1cm}
\addtolength{\evensidemargin}{-1cm}
\addtolength{\textwidth}{2cm}
\addtolength{\textheight}{25cm}
\parindent=0pt
\parskip=1em
\pagestyle{empty}

\begin{document}
\vspace{-8cm}
\begin{center}
{\huge RAND-Seminar \\*[1,0cm]

Montag, 28. April 1997, 11 Uhr c.t.\\*[1,0cm]
Seminarraum 327\\*[2,0cm]

''Schnelle randomisierte und parallele Algorithmen zum Auffinden von einfachen
Kreisen in Graphen''}\\*[1,5cm]

{\Large Carsten Dorgerloh, Universit\"at Bonn}\\*[1,5cm]
 
\end{center}
 
Zusammenfassung: 

Das Auffinden eines l\"angsten Kreises in einem Graphen $G$ ist ein hartes
Problem, da das Auffinden eines Hamiltonkreises $NP$-vollst\"andig ist.
Infolgedessen ist das Auffinden eines einfachen Kreises der L\"ange $k$ 
f\"ur ein beliebiges $k$ $NP$-vollst\"andig.
Dies gilt sogar dann, wenn $G$ planar ist und unter anderen Einschr\"ankungen.
Daher widmet man dem folgendem Problem besondere Aufmerksamkeit:
Dem Auffinden von einfachen Kreisen einer gegebenen L\"ange. 
Wir zeigen, da\3 ein einfacher Kreis einer gegebenen L\"ange $k$ in 
einem planaren Graphen, wenn einer existiert, von einer randomisierten 
EREW-PRAM berechnet werden kann. Der Erwartungswert der Laufzeit des Algorithmus 
betr\"agt $O(\log n)$ unter Verwendung von $O(n)$ Prozessoren.
K\"urzlich haben wir einen randomisierten sequentiellen Algorithmus
entwickelt, der dieses Problem f\"ur allgemeine Graphen in 
$O(max\{m, n \log n\})$ erwarteter Laufzeit l\"ost. Dieser Algorithmus kann
mit einem geringen Verlust an Effizienz derandomisiert werden. Dar\"uber
hinaus l\"a\3t sich der randomisierte Algorithmus derart parallelisieren,
so da\3 er das obige Ergebnis f\"ur planare Graphen verallgemeinert.

Gemeinsame Arbeit mit {\bf J\"urgen Wirtgen}.
\end{document}





