• Date: Fri, 29 Jun 2012, 14:00
• Location: SR 301
• Speaker: Shunsuke Inenaga, Kyushu University

• Date: Fri, 1 Jun 2012, 14:00
• Location: SR 301
• Speaker: David Oertel
• Inhalt: Das Problem des Ausbaus von Hochspannungsnetzen in einem vereinfachenden mathematischen Modell ist wie folgt definiert. Gegeben ein Hochspannungs-Netz aus Erzeugern und Verbrauchern (abstrahiert als Knoten), die durch Stromleitungen (Kanten) verbundensind: An welchen Stellen sollen mit möglichst geringen Kosten neue Leitungen eingefügt werden, sodass vorgegebene maximale Belastungender Leitungen nicht überschritten werden? Dieses Problem ist in der ursprünglichen Formulierung als mixed-integer non-linear programNP-schwer, da es als Untermenge das Steinerbaumproblem enthält.Durch Gebrauch der Theroie über elektrische Netzwerke wird gezeigt, warum das Problem weiterhin NP-schwer ist, wenn die Unterklasse vonSteinerbäumen ignoriert wird, indem nur (hochgradig) zusammenhängende Graphen betrachtet werden und der Fokus auf die Einhaltung dermaximalen Kantenbelastung gelegt wird. Diese Einschränkung spiegelt den realistischeren Fall wider, wenn ein lange existierendesHochspannungsnetz wegen eines steigenden zukünftigen Strombedarfs erweitert werden muss. Die algorithmische Schwierigkeit wirdbewiesen, indem gezeigt wird, dass dieses Problem algorithmisch äquivalent zu $3$-SAT ist.Darüberhinaus wird gezeigt, wie viel Aufwand für Berechnung und Implementierung wirklich nötig ist, um realistische Szenarios in der Praxis zu lösen.

• Date: Tue, 22 May 2012, 14:30
• Location: SR -120
• Speaker: Neil Jami, Diplomarbeiter

• Date: Tue, 22 May 2012, 14:00
• Location: SR -120
• Speaker: Jonathan Rollin, Studienarbeiter
• Inhalt: Ein gegebener Graph soll durch Einfügen neuer Kanten so erweitert werden, dass bestimmte zusätzliche Eigenschaften erfüllt werden. Genauer gesagt soll hier die Planarität eines Graphen erhalten bleiben, wenn durch zusätzliche Kanten 3-Regularität erreicht wird. Darüber hinaus soll wenn möglich auch der Zusammenhang verstärkt werden. Es stellt sich heraus, dass es NP-schwer ist zu entscheiden, ob eine solche Menge von neuen Kanten für einen gegebenen planaren Graphen existiert. Das Problem bleibt sogar dann NP-schwer, wenn als Eingabeinstanzen nur bereits 2-fach zusammenhängende Graphen betrachtet werden. Beschränkt man sich jedoch darauf, dass die neuen Kanten nur innerhalb der Facetten einer gegebenen planaren Einbettung eingefügt werden dürfen, so reduziert sich die Komplexität des Problems deutlich. Es wird gezeigt, dass sich dieses Problem auf ein Matchingresultat reduzieren lässt. Die Existenz einer solchen 3-regulären (und 2-fach zusammenhängenden) Erweiterung ist äquivalent zur Existenz eines Matchings in einem bestimmten Graphen und somit effizient berechenbar. Für diesen Fall wird zudem ein Algorithmus zur Berechnung einer 3-regulären und 2-fach zusammenhängenden Erweiterung vorgestellt.

• Date: Fri, 18 May 2012, 14:00
• Location: SR 301
• Speaker: Daniel Patejdl
• Inhalt: Graphen eignen sich nicht nur zur algorithmichen Lösung von Problemen, sondern auch dazu, in visualisierter Form Zusammenhänge für das menschliche Auge darzustellen. Eine Variante der Darstellung ist die Einbettung von Graphen in Gitter. Das Standard-Gitter ist das orthogonale Gitter, welches durch horizontal und vertikal verlaufende Linien konstruiert wird. In dieser Arbeit werden Einbettungen von Graphen auf Nichtstandard-Gitter betrachtet, die bisher nur rudimentär erforscht sind. Zum einen das Bienenwabengitter, eine Anordnung von regulären, zusammenhängenden Sechsecken, auf dem verschiedene Algorithmen zum Zeichnen von Bäumen präsentiert werden. Die von den Algorithmen auf dem Gitter gezeichneten Bäume werden anschließend hinsichtlich ihres Platzverbrauchs, ein häufig auftretendes Optimierungskriterium, analysiert. Zum anderen wird ein regulär trianguliertes Gitter, auch hexagonales Gitter genannt, thematisiert. Das hexagonale Gitter kann durch eine Erweiterung des Bienenwabengitters um Diagonalen konstruiert werden. Durch eine Scherung des Gitters erhält man ein Gitter, welches strukturelle Ähnlichkeiten zum orthogonalen Gitter aufweist. Diese Ähnlichkeiten erlauben es, bekannte algorithmische sowie komplexitätstheoretische Ergebnisse vom orthogonalen auf das hexagonale Gitter zu übertragen. Es wird unter anderem ein effizienter Algorithmus vorgestellt, der zu bestimmten 4-planaren Graphen eine Einbettung in eine gegebene Punktmenge auf dem hexagonalen Gitter berechnet. Dabei wird die Einbettung so gewählt, dass alle Kanten durch kürzeste Wege realisiert sind. Des Weiteren wird gezeigt, dass das Problem, welches der Algorithmus für spezielle Graphen effizient löst, im Allgemeinen NP-schwer ist.

• Date: Wed, 16 May 2012, 14:00
• Location: SR 301
• Speaker: Christos Zaroliagis, University of Patras
• Inhalt: An ad-hoc mobile network is a collection of mobile hosts with wireless network interfaces forming a temporary network without the aid of any established infrastructure or centralized administration. In an ad-hoc network two hosts that want to communicate may not be within the wireless transmission range of each other, but could communicate if other hosts between them are also participating in the ad-hoc network and are willing to forward packets for them. The most common way to establish communication is to form paths of intermediate nodes (hosts), where it is assumed that there is a link between two nodes if the corresponding hosts lie within one another's transmission radius and hence can directly communicate with each other. In wide area ad-hoc networks, however, a sufficiently long communication path is difficult to establish and/or maintain. Single link failures, happening when a small number of users that were part of the communication path move in a way such that they are no longer within the transmission range of each other, make the path invalid. In this lecture, we shall investigate a different approach to establish basic communication in ad-hoc mobile networks. The main idea is to take advantage of the mobile hosts natural movement by exchanging information whenever mobile hosts meet incidentally. In particular, two protocols will be presented that are based on the semi-compulsory approach, according to which a small part of the mobile users that moves in a predetermined way is used as an intermediate pool for receiving and delivering messages. The practical assessment of the protocols will be also discussed.

• Date: Tue, 15 May 2012, 14:00
• Location: SR -120
• Speaker: Philipp Schneider, Studienarbeiter
• Inhalt: Eine spezielle Sorte von Netzwerkerweiterungsproblemen, nämlich die Frage, wie man einen gegebenen Punkt (Feed-node) innerhalb einer Facette eines Netzwerkes, dargestellt als Rand eines einfachen Polygons, mit diesem sinnvoll verbinden kann, wurde von Aronov et al. behandelt. Aronov et al. ziehen die Streckung als Maß der Güte einer oder mehrerer Verbindungen (Feed-links) des Punktes mit dem Rand des Polygons heran. Dieses Gütemaß spiegelt den relativen Umweg wieder, den man über das Netzwerk und den Feed-link im Vergleich zum direkten Weg nehmen muss. Aronov et al. Stellen heraus, dass die Frage nach der optimalen Platzierung von mehr als einem Feed-link in einfachen Polygonen ungeklärt bleibt. Wir werden einen Spezialfall dieses Problems lösen, nämlich die effiziente optimale Platzierung von zwei Feed-links bezüglich einer gegebenen, endlichen Menge von Sites. Außerdem werden wir eine abgeänderte Problemstellung betrachten, in der rektilineare, einfache Polygone gegeben sind (das sind einfache Polygone mit lediglich horizontalen und vertikalen Kanten), für die wir rektilineare Feed-links (das sind kürzeste Wege aus lediglich horizontalen und vertikalen Kanten) vom Feed-node an den Rand des Polygons suchen, so dass die Streckung gemessen mit der L1-Metrik minimal wird.

• Date: Mon, 14 May 2012, 10:00
• Location: SR 236
• Speaker: Roger Wattenhofer, ETH Zürich
• Inhalt: The title of my presentation is a motto originally coined in urban design about 100 years ago, but used in various different contexts since. The motto can also be applied to many areas in computer science. For instance, in computational game theory, each agent tries to maximize his/her own (local) benefit, and we analyze the (global) social welfare. Also, computer architecture is designed for locality of reference. Recently, the distributed computing community has made tremendous progress towards understanding the complexity of distributed message passing algorithms. In networks, a rich selection of upper and lower bounds regarding how much time it takes to solve or approximate a problem have been established; we now have a good understanding how local actions and global goal influence each other. This distributed complexity theory may ultimately help to give the "think global, act local" motto a mathematical foundation. In my talk I will introduce the message passing model, present a few selected results, mention prominent open problems, and discuss some of the most exciting future research directions. Upcoming applications may not necessarily lie in computer science but rather in other areas that deal with networked systems, e.g. biology or social sciences.

• Date: Fri, 11 May 2012, 14:00
• Location: SR 301
• Speaker: Morteza Monemizadeh
• Inhalt: Recent developments \cite{BSS08,CSS09,HKNO09,NO08} in the area of testing properties for classes of bounded-degree graphs with an excluded minor propose a new technique called \textit{partitioning oracles}. A partitioning oracle explores local neighborhoods of sampled vertices and using this, answers queries about a global partition that breaks the graph into small connected components by removing only a small fraction of the edges. We take the idea of partitioning oracles as the first step to connect property testing algorithms to streaming algorithms. In this paper, we focus on the \emph{Euclidean facility location problems} as a test case. Given a point set $P = \{p_1, \dots, p_n\}$ of size $n$ in the plane $[\Delta]^2=\{0,1,\dots,\Delta\}^2$ and $f \in \Re^+$, the facility location problem is to find a set $F \subseteq [\Delta]^2$ of facilities such that % \begin{displaymath} \mathrm{cost}(P,F)=\sum_{p \in P} \dist(p,F)+|F|\cdot f \end{displaymath} % is minimized, where $\dist(p,F)=\min_{q \in F} \dist(p,q)$ is the distance of $p$ to the nearest facility in $F$. We show that there is a partitioning $\IN$ of the plane into regions (called isolated neighborhoods) by removal of small regions (called borders) surrounding isolated neighborhoods. By putting $\epsilon\cdot |F|$ artificial facilities inside the borders of the regions of $\IN$ we are able to disconnect each isolated neighborhood from its outside and by solving the facility location problem inside each isolated neighborhood and its border and taking the union of the solutions we find a new PTAS for this problem. Then we show that there is an oracle for the partitioning $\IN$ which can be implemented in the turnstile streaming model using $\mathrm{poly}(\epsilon^{-1}\log\Delta)$ space. This in turn gives a $(1+\epsilon)$-approximation to the cost of the Euclidean facility location problem in the turnstile streaming model using $\mathrm{poly}(\epsilon^{-1}\log\Delta)$ space solving this major open problem in the streaming model after seven years.

• Date: Fri, 27 Apr 2012, 14:30
• Location: SR 301
• Speaker: Roman Zubkov, Bachelorarbeiter
• Inhalt: In dieser Arbeit wird gezeigt, wie die Beschreibung einer Route im Straßennetz komprimiert dargestellt werden kann. Ein Szenario wird zugrunde gelegt, indem ein Klient (z. B. ein Navigationsgerät) eine Anfrage nach einer Route von einem Startpunkt zu einem Zielpunkt an einen Server sendet. Der Server besitzt statistische Verkehrsinformationen, mit denen er eine optimale Route berechnet. Er komprimiert sie und sendet sie an den Klienten. Um die Route möglichst kompakt zu komprimieren, wird sie in möglichst große eindeutige kürzeste Pfade zerlegt. Der Knoten, an dem einer dieser kürzesten Pfade endet und der nächste kürzeste Pfad beginnt, wird Viaknoten genannt. Die Sequenz der Viaknoten bildet die komprimierte Route. Um die Viaknoten zu finden, werden vier verschiedene Strategien ausgearbeitet. Die erste Strategie ist eine Modifikation des Algorithmus von Dijkstra, die einen maximalen eindeutigen kürzesten Präfixpfad eines Pfades berechnet. Zur Beschleunigung der Kompression und Dekompression wird eine Contraction Hierarchie (CH) verwendet. Mit Hilfe einer modifizierten Punkt-zu-Punkt-Anfrage der CH werden drei weitere Strategien entwickelt. Zu jeder Kompressionsstrategie werden Experimente durchgeführt und evaluiert. Die Kompressionsrate bleibt dabei unter 1,7% und die Kompressionszeit bei der schnellsten Strategie unter 50 ms, selbst bei größtmöglichen, kürzesten Routen im deutschen Straßennetz. Diese Arbeit greift die Idee von Viaknoten von G. V. Batz et al. auf und baut sie aus. Zusätzliche Algorithmen werden entwickelt, die Kompressionsverfahren werden an die CH angepasst, Beweise für theoretische Aussagen werden geliefert und alle Algorithmen werden implementiert und evaluiert.

• Date: Fri, 20 Apr 2012, 14:00
• Location: SR 301
• Speaker: Fabian Fuchs, Diplomarbeiter
• Inhalt: In Drahtlosnetzwerken steht üblicherweise nur eine begrenzte Menge Energie zur Verfügung. Da die Kommunikation in Drahtlosnetzwerken einen Großteil der Energie verbraucht, wurden in den letzten Jahren viele Möglichkeiten untersucht Kommunikation effizienter zu gestalten - vor allem in Bezug auf Energie- und Störungsminimierung. Eine der Möglichkeiten ist das Einteilen der Übertragungen in Zeitslots (sog. TDMA Schedules). In dieser Arbeit vergleichen wir den erreichbaren Datendurchsatz für Medienzugriff via TDMA Schedules mit dem Medienzugriff mittels des CSMA/CA Mechanismus mit Hilfe des Netzwerksimulators ns-3 und untersuchen die Auswirkungen eines bidirektionalen Interferenzmodells auf die Effizienz der TDMA Schedules. Eine andere Möglichkeit den Energieverbrauch sowie Störungen zu reduzieren bietet Topologiekontrolle. Hierbei werden die Kommunikationsverbindungen des Netzwerks auf eine Auswahl beschränkt und (wenn möglich) die Sendeleistung reduziert. Viele Algorithmen für Topologiekontrolle wurden bisher hauptsächlich theoretisch betrachtet. In dieser Arbeit werden die Algorithmen in Hinblick auf Datendurchsatz sowie Energieverbrauch mittels des Netzwerksimulators ns-3 untersucht.

• Date: Fri, 23 Mar 2012, 14:00
• Location: SR 301
• Speaker: Christian Wellenbrock, Studienarbeiter
• Inhalt: Bei der Visualisierung großer Graphen stoßen automatische Layoutalgorithmen schnell an ihre Grenzen. Will man bestimmte Strukturen, Subgraphen oder Symmetrien hervorheben, müssen oft große Teile des Graphen manipuliert werden. Wir betrachten konkret das Problem, in einem Graphen Platz für einen vorgegebenes Polygon zu schaffen, um dort etwa einen weiteren Teilgraphen einzufügen. Wir suchen also nach Einbettungen, in denen in einer bestimmten Facette Platz für dieses Polygon ist. Um die Wiedererkennbarkeit des ursprünglichen Layouts zu erhöhen, versuchen wir dabei die mittlere Längenänderung aller Kanten zu minimieren. Wir zeigen das dieses Problem in drei Varianten NP-schwer ist und stellen anschließend zwei heuristische Algorithmen zur approximativen Lösung vor.

• Date: Tue, 20 Mar 2012, 14:00
• Location: SR 301
• Speaker: Christof Doll, Diplomarbeiter
• Inhalt: Die Diplomarbeit beschäftigt sich mit automatisch generierten Layouts von Argumentkarten. Diese stellen Argumente einzelner Texte oder ganzer Debatten sowie deren Beziehungen zueinander als Graphstruktur dar. Sie finden hauptsächlich innerhalb der Geisteswissenschaft ihre Anwendung. Die Arbeit beginnt mit einer empirischen Analyse der graphentheoretischen Eigenschaften von Argumentkarten. Darauf aufbauend definieren wir die Anforderungen an Layouts von Argumentkarten sowie die zu optimierenden Kriterien. Grundlegend sollen die gewünschten Layouts orthogonale Aufwärtszeichnungen sein. Daneben fordern wir, dass die Zeichenfläche in disjunkte Spalten unterteilt ist, denen dann einzelne oder mehrere Knoten zugeteilt werden. Daher bezeichnen wir diese Layouts als Spalten-basiert. Bei der Erstellung der Layouts möchten wir die Kreuzungs- und Knickzahl, die Gesamtkantenlänge sowie die Distanz von Quellen und Senken zur äußeren Facette minimieren. Im Anschluss stellen wir einen auf dem Topology-Shape-Metrics-Framework basierender Algorithmus vor, der derartige Layouts berechnet. Dabei definieren wir die drei Schritte des Frameworks formal und untersuchen sie einzeln in Bezug auf ihre Komplexität. Der Topology- und Metrics-Schritt erweisen sich als NP-vollständig, während wir für den Shape-Schritt die NP-Vollständigkeit nur vermuten können. Aus diesen Gründen werden die wichtigsten Schritte der Layoutberechnung heuristisch gelöst. In einer anschließenden Untersuchung der berechneten Layouts stellen wir jedoch fest, dass die Optimierungskriterien hinreichend gut minimiert werden. Darüber hinaus überzeugen diese Layouts auch aufgrund ihrer Ästhetik und der übersichtlichen Struktur.

• Date: Fri, 2 Mar 2012, 14:00
• Location: SR 301
• Speaker: Maximilian Schuler, Bachelorarbeiter
• Inhalt: Viele modernen Graphpartitionierungsalgorithmen verwenden ein Mehrlevelverfahren, das aus drei Phasen besteht: Zunächst wird eine Hierarchie von Schrittweiße gröberen Graphen erstellt, woraufhin der gröbste Graph initial partitioniert wird und zuletzt wird für jeden feineren Graphen die Partitionierung verbessert. Da die Vergröberungsphase essentiell für ein gutes Ergebnis ist, werden in diesem Vortrag neue Techniken vorgestellt die in dieser Phase des Algorithmuses anwendung finden. Hierbei liegt das Hauptaugenmerk auf der Konstruktion neuer Kantenbewertungsfunktionen und der Analyse und dem Entwurf eines neuen approximativen Paarungsalgorithmuses. Alle Ergebnisse werden mithilfe des Merhlevel-Graphpartitionierers KaFFPa ausgewertet. Es wird sich zeigen, dass gerade bei der Partitionierung von sozialen Netzwerken signifikante Verbesserungen der Partitionisqualität erziehlt werden können.

• Date: Tue, 7 Feb 2012, 14:30
• Location: SR 301
• Speaker: Roland Gröll, Studienarbeiter
• Inhalt: Die Corestruktur hat sich als interessantes Maß in der Netzwerkanalyse herrausgestellt. In dieser Studienarbeit wurde untersucht, wie man die Corestruktur eines Graphen mit möglichst wenigen Kantenadditionen verbessern kann. Es stellte sich heraus, dass es möglich ist in polynomieller Zeit den gesamten Graphen in den k-Core zu bringen. Schränkt man die Menge der Knoten, die man in einem gewissen Core haben möchte jedoch auf eine vorher festgelegte Teilmenge ein, ist das Problem NP-schwer, selbst für den k-core mit k = 3, jedoch polynomiell lösbar für kleinere k.

• Date: Tue, 7 Feb 2012, 14:00
• Location: SR 301
• Speaker: Jan-Christoph Athenstädt, Studienarbeiter
• Inhalt: Die Studienarbeit stellt ein Verfahren zur Visualisierung von großen, geclusterten Graphen (> 10.000 Knoten) vor. Zunächst wird ein 2D-Layout unter Berücksichtigung der bestehenden Hierarchie aus Clustern generiert, welches dann im zweiten Schritt in 3D mit Hilfe einer Landschafts-Metapher dargestellt wird. Für das 2D-Layout wird ein kräftebasiertes Verfahren auf Basis des Fruchterman-Reingold-Algorithmus verwendet. Ziel ist es hierbei, sowohl einzelne Knoten und Kanten als auch die Gesamtstruktur und die verschiedenen Clusterebenen darzustellen. Die 3D-Landschaft wird mit Hilfe eines Gauss-Filters als Höhenfeld über dem 2D-Layout generiert. Dabei können verschiedene Charakteristiken des Layouts, wie zum Beispiel die Knotendichte oder der durchschnittlichen Knotengrad als Höheninformation dargestellt werden. Der ursprüngliche Graph wird anschließend über die Landschaft gelegt, wobei geradlinige Kanten die Knoten verbinden.

• Date: Fri, 27 Jan 2012, 14:00
• Location: SR 301
• Speaker: Jan-Ole Sasse, Diplomarbeiter

• Date: Tue, 24 Jan 2012, 14:30
• Location: SR 301
• Speaker: Geraud Oscar Fofie Lafou, Diplomarbeiter
• Inhalt: In dieser Arbeit geht es darum, zu untersuchen, welcher Clusteringalgorithmus bessere Clusterungen liefert. Dabei werden besonders Clusteringalgorithmen betrachtet, die mehrere Clusterungen verschiedener Grobheit liefern. Die Algorithmen werden miteinander anhand von Zufallsgraphen verglichen. Der Vergleich besteht darin, zu untersuchen, wie gut jeder Algorithmus die Referenzclusterungen in Zufallsgraphen wiedererkennt. Dafür werden Zufallsgraphen erzeugt, die mehrere Clusterungen enthalten. Die Clusterungen in Zufallsgraphen enthalten sich gegenseitig (hierarchische Clusterungen) oder überlappen sich gegenseitig (sich überlagernde Clusterungen). Ein großer Teil der Arbeit besteht darin, einen effizenten Algorithmus zu entwickeln, der solche Zufallsgraphen erzeugt.

• Date: Tue, 24 Jan 2012, 14:00
• Location: SR 301
• Speaker: Tobias Haaß
• Inhalt: In der Bachelorarbeit geht es um das Visualisieren standortgebundener Infrastrukturprojekte, die als soziales Netzwerk modelliert werden. Zunächst wird das Projekt als Graph modelliert. Für die Zeichnung wird jedem Knoten eine initiale Position zugeordnet, die von seinem Herkunftsort aus der Realität abhängt. Bei den betrachteten Projekten hat sich gezeigt, dass sich viele Akteure am Projektstandort ansammeln. Um für eine bessere Übersicht zu sorgen, wird die nähere Umgebung um den Standort entzerrt. Des Weiteren werden Knotenüberlappungen mit einem kräftebasierten Algorithmus aufgelöst. Abschließend werden für jeden Knoten Beschriftungen eingefügt und eine Position für diese berechnet. Um die Struktur des Graphen zu analysieren wird das Projekt als Correlation-Clustering Problem betrachtet und ein ganzzahliges lineares Optimierungsproblem gelöst.

• Date: Fri, 20 Jan 2012, 14:00
• Location: SR 301
• Speaker: Michael Hamann, Bachelorarbeiter
• Inhalt: Die Qualitätsbewertung von Clusterungen ist eine schwierig zu formalisierende Aufgabenstellung, was sich insbesondere in der Existenz einer Vielzahl von verschiedenen Qualitätsmaßen ausdrückt. Der schnittbasierte Cut-Clustering-Algorithmus von Flake et al. erzeugt abhängig von einem Parameter hierarchisch verschachtelte Clusterungen. Diese zeichnen sich durch eine Qualitätsgarantie bezüglich des Maßes intra-cluster-Expansion aus, welches im allgemeinen schwer zu berechnen ist. Diese Arbeit stellt ein Verfahren vor, das systematisch alle verschachtelten Clusterungen, die mit Hilfe des Cut-Clustering-Algorithmus erzeugt werden können, findet und untersucht experimentell die Aussagekraft der gegebenen Qualitätsgarantie im Vergleich mit trivialen Schranken. Des weiteren bewertet sie die Qualität der Clusterungen bezüglich des gängigen Maßes Modularity und vergleicht die Ergebnisse mit jenen eines modularity-basierten Greedy-Algorithmus, der im Gegensatz zum Cut-Clustering-Algorithmus explizit versucht Modularity zu optimieren.

• Date: Wed, 21 Dec 2011, 11:30
• Location: SR 236
• Speaker: Samitha Samaranayake, UC Berkeley
• Inhalt: Optimal routing in transportation networks can be a challenging problem when considering the stochastic nature of link travel-times. Therefore, it is common to use the expected value of link travel-times as a sufficient statistic and ignore the variance, even though route reliability is an important decision factor in many applications. In this presentation, we consider the following optimality criterion: maximizing the probability of arriving on time at a destination given a departure time and a time budget, and show how to efficiently generate an optimal routing policy. One of the complexities of this problem is the fact that the optimal routing policy could contain loops. We propose a dynamic programming based solution that finds an optimal policy by first computing an optimal order in which to solve the dynamic program. Experimental results are presented for practical scenarios in the San Francisco Bay Area.

• Date: Fri, 2 Dec 2011, 14:00
• Location: SR 301
• Speaker: Jonathan Dimond, Studienarbeiter
• Inhalt: Mit einer immer stärker vernetzten Welt steigt das Bedürfnis, aus veschiedensten Netzwerken Informationen zu gewinnen. In den letzten Jahren gewann das Problem des Community Clusterings zunehmend an Bedeutung. Für riesige Graphen mit Milliarden von Knoten kann dies eine unlösbare Aufgabe bedeuten. Wir betrachten das inverse Problem. Für gegebene Knoten soll ein Subgraph extrahiert werden, der eine sinnvolle Community darstellt. Wir betrachten dafür Random Walks und eine verwandte aber neuartige Methode, die wir Similarity Propagation nennen, und analysieren ihre Güte anhand von Conductance. Zusätzlich analysieren wir, wie sich für dieses Problem etablierte Verfahren für einen dynamischen Graphen anpassen lassen. Darüber hinaus stellen wir einen Graph Generator vor, der in der Lage ist, effizient riesige Graphen mit günstigen Eigenschaften wie Power-Law Kantengradverteilungen und Community-Struktur zu generieren.

• Date: Wed, 23 Nov 2011, 13:00
• Location: SR 236
• Speaker: Prof. Lawrence Mandow, Universidad de Malaga (Spain)
• Inhalt: The shortest path problem has been widely studied in the past, and a variety of algorithms have been proposed. Most of them are variants of Dijkstra’s or A* algorithms. Many recent studies are focused on their application in car navigation systems. These software systems give the best route to a destination point according to a single criterion, like the minimization of time. Additional criteria, like distance or economic cost, are considered in general only in a weighted form. The Multiobjective Shortest Path Problem explicitly considers the simultaneous optimization of several objectives. The problem no longer has a single optimal solution but a set of efficient, or Pareto-optimal solutions. The number of efficient solutions is known to grow exponentially with graph size in the worst case. However, in certain classes of problems the number of efficient solutions can be shown to grow only polynomially with goal depth in the worst case. Several extensions to Dijkstra’s or A* algorithm have been devised to solve the problem. The former’s most known extension is due to Martins. This talk covers the proposed extensions of A* to multiobjective search, namely MOA*, NAMOA*, and Tung & Chew’s algorithm. Formal properties and empirical evaluations will be discussed. The use of adequate heuristics can be very beneficial in certain cases in terms of space and time performance. An overview of key aspects about heuristics in multiobjective A*-like algorithms will be provided, and their application to route planning in road maps will be discussed.

• Date: Tue, 22 Nov 2011, 13:30
• Location: SR 301
• Speaker: Heiner Zille, Bachelorarbeiter
• Inhalt: Diese Arbeit beschäftigt sich mit der Berechnung möglichst einfacher Routen als Alternativen zu kürzesten Routen. Im Gegensatz zu früheren Arbeiten sollen einfachste Routen unter der Nebenbdingung gefunden werden, dass diese eine gewisse Maximallänge im Vergleich zum kürzesten Weg nicht überschreiten. Die entwickelten Verfahren wurden implementiert und evaluiert mit Hinsicht auf den Anwendungsfall: Schematische Darstellung von Routen.

• Date: Fri, 11 Nov 2011, 13:15
• Location: SR 301
• Speaker: Moritz Baum, Diplomarbeiter
• Inhalt: Viele bekannte Beschleunigungstechniken zur Routenplanung gewähren Freiheitsgrade in der konkreten Umsetzung ihrer Vorberechnung, deren Ausfüllung großen Einfluss auf die Performanz späterer Kürzeste-Wege-Anfragen haben kann. Im Falle von Arc-Flags besteht dieser Freiheitsgrad in der Wahl einer Partition des Eingabegraphen. Ein gängiges Maß zur Bewertung der Qualität einer solchen Partition ist die Betrachtung der erwarteten Suchraumgröße einer zufälligen Anfrage. Die Berechnung einer Partition, die den erwarteten Suchraum minimiert, ist im Allgemeinen $\mathcal{NP}$-schwer. Ausgehend von diesem Resultat liegt der Schwerpunkt dieser Arbeit auf einer ausführlichen theoretischen Untersuchung dieses Problems. Zunächst wird dazu der Einfluss verschiedener eingeschränkter Graphklassen auf die Schwierigkeit der Berechnung einer optimalen Lösung untersucht. Insbesondere wird dabei gezeigt, dass das Problem selbst auf Bäumen $\mathcal{NP}$-schwer bleibt. Zudem werden ganzzahlige lineare Programme zur Berechnung optimaler Partitionen entwickelt und diskutiert. Anschließend werden zwei Polynomialzeit-Algorithem basierend auf dem Greedy-Ansatz vorgestellt.

• Date: Mon, 7 Nov 2011, 13:00
• Location: SR 236
• Speaker: Alejandro Salinger, University of Waterloo
• Inhalt: Paging for multi-core processors extends the classical paging problem to a setting in which several processes simultaneously share the cache. While cache eviction policies have been widely studied both in theory and practice for sequential processors, in the multi-core case the performance of even the most common eviction policies is not yet fully understood. In particular, there is almost no theoretical backing for the use of current eviction policies in multi-core processors. Recently, Hassidim proposed a model for multi-core paging, showing that LRU is not competitive against an offline policy that has the power to arbitrarily delay request sequences to its advantage. We propose a more realistic model in which requests must be served as they arrive. We study the problem of minimizing the number of faults, deriving bounds on the competitive ratios of natural strategies to manage the cache. We show that traditional online paging algorithms are not competitive in our model. We then study the offline paging problem and show that the problem of deciding if a request can be served such that at a given time each sequence has faulted at most a given number of times is NP-complete and that its optimization version is APX-hard (for an unbounded number of sequences). Lastly, we describe offline algorithms for the decision problem and for minimizing the total number of faults that run in polynomial time in the length of the sequences. This is joint work with Alejandro Lopez-Ortiz

• Date: Fri, 28 Oct 2011, 14:00
• Location: SR 301
• Speaker: Alex Lopez-Ortiz, University of Waterloo
• Inhalt: In this talk we journey through three related subjects: 1) Paging algorithms. It has long been known that competitive analysis fails to reflect actual performance of paging algorithms in practice. We show that this can easily be fixed by a more careful definition of the denominator in the computation of the competitive ratio. The new measure, called parameterized analysis accurately predicts the performance of well known paging and list update algorithms. 2) Paging for multicore computers. We show that, surprisingly, this problem shares little with its sequential version and that good sequential algorithms exhibit rather bad performance in the multicore case. In particular we show that the offline optimum is NP-complete to compute, in contrast to the sequential case where the optimum is the well known Furthest-in-The-Future FTF algorithm (also known as LFD). 3) Multicore computing models. The widespread introduction of multicore computers marked the first time in fifty years in which the model of computation used by theoreticians (i.e. the RAM model) failed to reflect real life computers in which actual algorithms are run. This gap will only increase as the number of cores continues to grow. We then introduce a model of low degree parallelism which reflects modern multicore architectures while doing away with the main difficulties and drawbacks that plagued the PRAM model. We give a series of practical and theoretical arguments why this low degree assumption is critically important as well as realistic.

• Date: Tue, 25 Oct 2011, 14:00
• Location: SR 301
• Speaker: Jan-Hinrich Kämper, Diplomarbeiter

• Date: Fri, 21 Oct 2011, 14:30
• Location: SR 301
• Speaker: Christian Staudt, Diplomarbeiter
• Inhalt: Im Bereich Scientometrie ist die Analyse von Netzwerken, insbesondere Zitations- und Kollaborationsnetzwerken, zu einem wichtigen Werkzeug geworden. Kollaborationsnetzwerke sind auch Gegenstand dieser Arbeit: Auf Grundlage der Publikationsdatenbank DBLP werden die Beziehungen zwischen Publikationen und Autoren als Graphen modelliert. Standardtechniken der Analyse von (sozialen) Netzwerken (Zusammenhang, Gradverteilung, k-Core-Zerlegung) ergeben ein allgemeines Bild des Netzwerkes. Im Zentrum steht die Frage, ob und wie das Netzwerk von akademischen/sozialen Ereignissen geformt wird: Die Dagstuhl-Seminare haben das Ziel (kollaborative) Arbeit in innovativen Gebieten der Forschung zu fördern. Ihre Spuren in der Struktur des Netzwerkes werden mithilfe von Teilnehmerdaten untersucht. Außerdem liefert die Arbeit ein Beispiel für Modularity-Clustering auf einem empirischen Graphen, und behandelt die Frage, ob sich "kollaborative Cluster" aufgrund thematischer Ähnlichkeiten bilden. Schließlich wird untersucht, ob Eigenvektorzentralität im Kollaborationsgraphen geeignet ist, um fachlich einflussreiche Autoren zu identifizieren.

• Date: Fri, 21 Oct 2011, 14:00
• Location: SR 301
• Speaker: Gregor Stachowiak, Studienarbeiter

• Date: Wed, 19 Oct 2011, 17:30
• Location: Geb. 50.34, HS -101
• Speaker: Patrizio Angelini, Universita’ Roma Tre, Italy
• Inhalt: Given k planar graphs G1,...,Gk, deciding whether they admit a simultaneous embedding with fixed edges (SEFE) and whether they admit a simultaneous geometric embedding (SGE) are NP-hard problems, for k >= 3 and for k >= 2, respectively. In this talk we consider the complexity of the SEFE problem and of the SGE problem when graphs G1,...,Gk have a fixed planar embedding. In sharp contrast with the NP-hardness of SEFE for three non- embedded graphs, we show that the SEFE problem is polynomial-time solvable for three graphs with a fixed planar embedding. Furthermore, we show that, given k planar embedded graphs G1,...,Gk, deciding whether a SEFE of G1,...,Gk exists and deciding whether a SGE of G1,...,Gk exists are NP-hard problems, for k >= 14 and k >= 13, respectively.

• Date: Wed, 19 Oct 2011, 11:30
• Location: SR 236
• Speaker: Patrick Flick, BA-Arbeiter
• Inhalt: Ein Job ist malleable, wenn die von ihm benötigte Prozessorzahl nicht fix ist, und der Scheduler die Anzahl der dem Job zur Verfügung gestellten Prozessoren zur Laufzeit ändern kann. In einem System mit vielen fixed-size Jobs gibt es meist Prozessoren, die nicht zugeteilt werden können, ihre Anzahl schwankt jedoch. Diese Prozessoren mit einem malleable Job zu nutzen, kann die Effizienz des Systems ohne weitere Eingriffe erhöhen. Das Sortieren ist eine Basisfunktionalität, die von vielen Programmen benötigt wird und oft einen hohen Anteil am Rechenaufwand dieser Programme hat. In der vorgestellten Arbeit wurde ein malleable Sortierer implementiert, und mit dem Multiway Mergesort aus der MCSTL verglichen.

• Date: Fri, 14 Oct 2011, 14:00
• Location: SR 301
• Speaker: Thomas Bläsius, Diplomarbeiter
• Inhalt: Ein PQ-Baum repräsentiert eine Menge von zyklische Ordnungen seiner Blätter, indem die Ordnung der Kanten um einen P-Knoten frei wählbar und um einen Q-Knoten bis auf Umkehrung festgelegt ist. Bei dem Problem {\sc Simultaneous PQ-Ordering} wird eine Menge von PQ-Bäumen betrachtet, deren Blätter zueinander in Beziehung stehen. Gesucht werden simultane Ordnungen für die Blätter aller PQ-Bäume, die sich mit den Beziehungen untereinander vertragen. Obwohl {\sc Simultaneous PQ-Ordering} im allgemeinen $\mathcal {NP}$-schwer ist, kann es für einfache Instanzen effizient gelöst werden. Dieses Ergebnis kann genutzt werden, um auf sehr einfache Weise das bedingte Einbettungsproblem {\sc Partially PQ-Constrained Planarity} für zweifach zusammenhängende Graphen und das Problem {\sc Simultaneous Embedding with Fixed Edges} für zweifach zusammenhängende Graphen mit zusammenhängendem Schnitt in Polynomialzeit zu lösen. Außerdem kann die Laufzeit des bisher schnellsten Algorithmus zum Erkennen von simultanen Intervallgraphen verbessert werden.

• Date: Fri, 9 Sep 2011, 14:00
• Location: SR 301
• Speaker: Thomas Gramer, Diplomarbeiter
• Inhalt: Delay Management beschäftigt sich mit der Frage, ob es besser ist auf ein verspätetes Fahrzeug zu warten oder nicht. Ziel dabei ist es, die Gesamtverspätung aller im Transportnetz beförderten Passagiere zu minimieren. Bisherige Verfahren berechnen die bestmögliche Gesamtverspätung, skalieren aber nicht für große Transportnetzwerke. Im Vortrag werden Verfahren vorgestellt, welche die Gesamtverspätung basierend auf lokaler Suche berechnen. Ziel dabei ist eine Beschleunigung der Berechnung gegenüber bestehenden ILP basierten Verfahren. Nicht optimale Lösungen werden somit zwar in Kauf genommen, lokale Suchverfahren scheinen aber dennoch geeignet zu sein, sehr nahe an die ILP basierten Lösungen heranzukommen.

• Date: Fri, 2 Sep 2011, 14:30
• Location: SR 301
• Speaker: David Lisowski, Diplomarbeiter

• Date: Fri, 2 Sep 2011, 14:00
• Location: SR 301
• Speaker: Florian Merz, Studienarbeiter
• Inhalt: Graphpartitionierung ist das Problem, die Knotenmenge eines Graphen in disjunkte, gleich große Teilmengen aufzuteilen, welche die Anzahl der Kanten zwischen diesen Teilmengen minimiert. In dieser Arbeit beschreiben wir einen Algorithmus, um große Zufallsgraphen generieren, zu denen wir eine optimale Partitionierung kennen. Um dies zu erreichen, generieren wir zuerst dichte Teilgraphen, für welche wir die untere Schranke für die Größe deren minimalen Schnittes kennen. Diese Teilgraphen verbinden wir danach mit einigen wenigen Kanten, so dass die durch die Teilgraphen induzierte Partitionierung optimal ist.

• Date: Fri, 26 Aug 2011, 14:00
• Location: SR 301
• Speaker: Roland Kluge, Bachelorarbeiter
• Inhalt: Um dynamische Cluster-Algorithmen evaluieren zu können, benötigt man Testdaten, die idealerweise aus der wirklichen Welt stammen. Leider sind große Testinstanzen selten und stehen zudem meist auch nicht frei zur Verfügung, was es schwierig macht, unterschiedliche Algorithmen oder deren Implementierungen auf einer gemeinsamen Testdatenbasis zu vergleichen. Diese Bachelorarbeit beschäftigt sich mit dem Entwurf und der Umsetzung eines effizienten Generators, der in der Lage ist, große Netzwerke sowie deren Entwicklung über zahlreiche Zeitschritten hinweg zu erzeugen.

• Date: Wed, 24 Aug 2011, 14:00
• Location: SR 236
• Speaker: Jan Wassenberg
• Inhalt: This talk will describe three techniques for speeding up integer sorting that result in the fastest currently known algorithm for shared-memory machines. Counting sort first determines the frequency of each key value, and then distributes successive items to the appropriate bins. We propose using virtual memory hardware as an `oracle' to designate the write position without requiring an initial scan over all items. Writing directly to a multitude of bins is inefficient on current and probably also future computer architectures. We describe the problem and show how to avoid it with write-combining. This technique is also applicable to other algorithms with frequent memory accesses. Write-combined virtual-memory counting sort is limited to small (e.g. 8-bit) keys. We show how to extend it to 32 or more bits and associate keys with an optional payload. A special ordering of the radix sorting passes improves locality on NUMA machines. The combination of these techniques results in software that outperforms a Fermi GPU when data-transfer overhead is included. Our implementation also outperforms Intel's radix sort by a factor of 1.64.

• Date: Fri, 1 Jul 2011, 14:00
• Location: SR 301
• Speaker: Raoul Steffen, Studienarbeiter ITI Sanders
• Inhalt: Naive implementations of external matrix multiplication will cause O(n^4) I/Os, where n is the side length of the matrices. I explain how to reduce the number of I/Os to O(n^3) with the side effect of simplifying transposition, too. Employing the Strassen-Algorithm, I try to further reduce I/Os and computation. Theoretical I/O-counts rsp. I/O-bounds including comparison of constant factors and test results are discussed for some algorithms.

• Date: Wed, 29 Jun 2011, 14:00
• Location: SR 236
• Speaker: Maarten Löffler, University of California Irvine
• Inhalt: We show that Delaunay triangulations and compressed quadtrees are equivalent structures. More precisely, we give two algorithms: the first computes a compressed quadtree for a planar point set, given the Delaunay triangulation; the second finds the Delaunay triangulation, given a compressed quadtree. Both algorithms run in deterministic linear time on a pointer machine. Our work builds on and extends previous results by Krznaric and Levcopolous and Buchin and Mulzer. Our main tool for the second algorithm is the well-separated pair decomposition (WSPD), a structure that has been used previously to find Euclidean minimum spanning trees in higher dimensions. We show that knowing the WSPD (and a quadtree) suffices to compute a planar EMST in linear time. With the EMST at hand, we can find the Delaunay triangulation in linear time. As a corollary, we obtain deterministic versions of many previous algorithms related to Delaunay triangulations, such as splitting planar Delaunay triangulations, preprocessing imprecise points for faster Delaunay computation, and transdichotomous Delaunay triangulations.

• Date: Wed, 22 Jun 2011, 14:00
• Location: SR 236
• Speaker: Prof. Paul Waddell, Berkeley
• Inhalt: This talk will describe a research project to integrate behavioral microsimulation of urban development and location of households, firms and real estate development, with procedural geometric modeling of urban landscapes including local streets, parcels, and buildings. By implementing an open source platform, called UrbanVision, to tightly couple approaches drawn from quite different domains, we strive to achieve novel means of modeling and analyzing the spatial structure and behavioral patterns within urban regions. Coupling this platform with microsimulation modeling of traffic is a research direction for the current project, but existing microsimulation traffic models generally lack sufficient computational performance for this tight integration to be very productive for operational use on large scale urban regions or even larger regions. The motivation for this work is to allow planners and the public to engage in planning efforts to reduce greenhouse gas emissions by reducing vehicle miles travelled. A policy strategy for this is, as adopted in state laws in California, is to reduce the need to drive by making walk and transit relatively more attractive modes, using a combination of land use and transportation policies.

• Date: Thu, 12 May 2011, 11:30
• Location: SR -118
• Speaker: Jochen Seidel, Diplomarbeiter
• Inhalt: In systems with Non-Uniform Memory Access (NUMA), memory bandwidth depends upon the memory location relative to the accessing processor. Each processing node can have its own local memory, but accesses foreign memory transparently in the same address space. Our approach is to minimize memory access time by scheduling jobs on the processing node where most memory access happens. We have implemented a working user-land scheduler favoring local memory access with a user interface similar to the one of Intel Thread Building Blocks (TBB). Furthermore, we devise a model to predict the effects of concurrently running jobs. We then show theoretically and in experiments, how efficiency can be gained by executing two di?erent jobs in parallel rather than sequentially. This implies the concurrent execution of more than one query in a DBMS can be advantageous.

• Date: Wed, 11 May 2011, 11:30
• Location: SR 236
• Speaker: Jochen Speck
• Inhalt: We give a fast algorithm for scheduling n tasks with flexible amount of parallelism on m processors, provided the speedup functions of the tasks are concave. We give efficient parallelizations of the algorithm that run in polylogarithmic time. Previous algorithms were sequential and required quadratic work. This is in some sense a best-possible result since the problem is NP-hard for more general speedup functions.

• Date: Wed, 20 Apr 2011, 14:00
• Location: SR 131
• Speaker: Christof Doll, Studienarbeiter
• Inhalt: Im Gegensatz zu vielen gängigen Clusterungsverfahren bietet schnittbasiertes Clustern die Möglichkeit, insbesondere für die Dichte innerhalb der Cluster eine untere Schranke anzugeben und damit eine bestimmte Qualität zu garantieren. Flake et al. entwickelten einen (statischen) hierarchischen schnittbasierten Ansatz, der Clusterungen verschiedener Granularität bezüglich des zugrundeliegenden Graphen erzeugt. Jede dieser Clusterungen bietet eine schnittbasierte Qualitätsgarantie. Diese Arbeit überträgt den hierarchischen Ansatz von Flake et al. in ein dynamisches Szenario, das Veränderungen der Kantengewichte im zugrundeliegenden Graphen zulässt. Der entwickelte dynamische Algorithmus erlaubt nach einer Veränderung (Gewichtserhöhung oder -reduktion) eine effiziente Neuberechnung der Clusterungshierarchie unter Beibehaltung der Qualitätsgarantie.

• Date: Tue, 22 Mar 2011, 14:00
• Location: SR 301
• Speaker: Edith Brunel, Diplomarbeiterin
• Inhalt: Graphen sind ein beliebtes Hilfsmittel zur Visualisierung von Daten und deren Zusammenhängen. Anzeigefläche und Auflösung limitieren allerdings die Darstellung großer Graphen, und es fällt meist viel Zeichenaufwand für Details an die ohnehin nicht erkennbar sind. Eine geeignete Generalisierung des Graphen, reduziert auf wesentliche visuelle und strukturelle Eigenschaften, kann oft nützlicher sein. Der Diplomarbeitsvortrag behandelt die schrittweise visuelle Abstraktion geometrischer Graphen (Graphen mit gegebenem 2D-Layout). Es werden grundlegende Probleme und Abstraktionstechniken, sowie spezialisierte Methoden zur Generalisierung der Knoten- und Kantenmenge solcher Graphen vorgestellt und diskutiert.

• Date: Thu, 17 Mar 2011, 10:30
• Location: SR 236
• Speaker: Dr. Jan-Henrik Haunert, Uni Würzburg
• Inhalt: In der Kartographie werden Landkarten traditionell in verschiedenen Maßstäben produziert. Dabei stellt sich oft das Problem, eine kleinmaßstäbige Karte aus einer großmaßstäbigen Karte abzuleiten. Wir diskutieren Optimierungsansätze für diese als Generalisierung bezeichnete Aufgabe und behandeln offene Probleme der Generalisierung, die sich z.B. bei kartographischen Darstellungen auf kleinen Displays ergeben.

• Date: Fri, 25 Feb 2011, 14:00
• Location: SR 301
• Speaker: Moritz von Looz, Studienarbeiter
• Inhalt: Wir beschreiben und implementieren einen Algorithmus, um digital-konvexe Regionen maximalen Gewichts in Graustufenbildern zu finden. Nachdem Christ et al. ein System für konsistente digitale Liniensegmente konstruierten, stellte sich die Frage nach entsprechenden digital-konvexen Regionen. Die vom Algorithmus berechneten Regionen sind gewichtsmaximal, der Zeitaufwand liegt bei O(n^5 log n). Mit zusätzlichen Eingabedaten zur Einschränkung des Suchraums kann diese Schranke zu O(n^3 log n) verbessert werden. Weiterhin beschreiben wir einen hybriden Approximationsalgorithmus, der sinnvolle Einschränkungen erzeugt indem der O(n^5 log n)-Algorithmus auf einer verkleinerten Version des Eingabebildes ausgeführt wird und anschließend diese Einschränkungen verwendet um die O(n^3 log n)-Schranke zu erreichen.

• Date: Fri, 28 Jan 2011, 14:00
• Location: SR 236
• Speaker: Robert Geisberger
• Inhalt: * Routing in öffentlichen Verkehrsnetzen: Routing mit realistischen Umsteigezeiten und vollständig realistisches Routing
  * Routing mit flexiblem Kantengewicht: Multikriterielles Kantengewicht (und Kantenrestriktionen)
  * Mehrere Start- und Zielknoten: Fahrgemeinschaften, (zeitabhängige Reisezeittabellen und Berechnung nächstgelegener Sonderziele)

• Date: Fri, 28 Jan 2011, 11:30
• Location: Geb. 50.20 (Durlacher Tor), SR 148
• Speaker: Christian Scheideler, Universität Paderborn
• Inhalt: In my talk I will consider the problem of designing simple medium access control (MAC) protocols for wireless networks that are provably robust against adaptive adversarial jamming. The wireless network consists of a set of honest and reliable nodes. In addition to these nodes there is an adversary who may know the protocol and its entire history and use this knowledge to jam the wireless channel at will at any time. However, in order to make sure that any messages can still be sent, we restrict the adversary to jam at most a (1-epsilon)-fraction of the time steps, for an arbitrarily small constant epsilon>0, and it has to make a jamming decision before it knows the actions of the nodes at the current step. The nodes cannot distinguish between the adversarial jamming or a collision of two or more messages that are sent at the same time. Nevertheless, I will demonstrate that there are local-control MAC protocols requiring only very limited knowledge about the adversary and the network that achieve a constant throughput for the non-jammed time steps under any adversarial strategy above. Our protocols also turn out to be very energy efficient and self-stabilizing.

• Date: Thu, 20 Jan 2011, 09:45
• Location: SR 236
• Speaker: Tamara Mchedlidze, National Technical University of Athens
• Inhalt: Upward Point-Set Embeddability is the problem of deciding whether a given upward planar digraph has an upward planar embedding into a given point set. While the undirected version of this problem has been extensively studied by the graph drawing community, the problem under consideration was defined in 2007 and still contains several important open problems. In this talk I give an overview of the results on the on Upward Point-Set Embeddability problem and present our recent results on it including:
  1. NP-completeness of the general problem.
  2. The proof of the fact that the classes of directed graphs upward-embeddable into every convex point-set and upward-embeddable into every general point-set do not coincide.
  3. Partial positive and negative results on embedding of directed paths into general point sets in and directed trees into convex point sets.

• Date: Fri, 26 Nov 2010, 14:00
• Location: SR 301
• Speaker: Emmanuel Müller
• Inhalt: In the knowledge discovery process, clustering is an established technique for grouping objects based on mutual similarity. However, in today's applications for each object very many attributes are provided. As multiple concepts described by different attributes are mixed in the same data set, clusters do not appear in all dimensions. In these high dimensional data spaces, each object can be clustered in several projections of the data. Subspace Clustering aims at detecting such clusters in any subspace projection. However, as the number of possible projections is exponential in the number of dimensions, the result is often tremendously large. In this talk, we discuss accurate but also efficient solutions to the general problem of redundancy in subspace clustering. We present a global optimization which detects the most interesting non-redundant subspace clusters. We prove that computation of this model is NP-hard. Thus, for an efficient computation we propose an approximative solution that shows high accuracy with respect to our relevance model.

• Date: Fri, 19 Nov 2010, 11:30
• Location: Geb. 50.20 (Durlacher Tor), SR 148
• Speaker: Roger Wattenhofer, ETH Zürich
• Inhalt: Having a common notion of time is a basic building block in many networks and distributed systems. In sensor networks, for instance, time synchronization is needed for locating events by trilateration, or for establishing an efficient media access control. The problem is well-studied, both in theory and practice. Nevertheless, several researchers have experienced and reported problems when trying to establish a common notion of time even in mid-scale networks. And also theoreticians all of a sudden started studying the problem again. In my talk, I will discuss clock synchronization from a theoretical point of view (published at FOCS, PODC, and JACM), as well as from a practical point of view (published at IPSN and SenSys). Hopefully I can surprise the audience with some unexpected impossibility results, and new protocols that improve the state of the art considerably. As such clock synchronization may serve as a good example where theory meets practice. I hope that the talk will be interesting to researchers with different backgrounds, such as networking, distributed systems, algorithms, or control theory.

• Date: Tue, 16 Nov 2010, 14:00
• Location: SR 301
• Speaker: Arash Farzan, MPI Saarbrücken
• Inhalt: We consider the problem of highly compact encoding of separable graphs. Separable graphs are those that admit a $O(n^c)$-separator theorem where $c < 1$. Our encoding supports navigation queries in constant time in the RAM with logarithmic word size. Namely, we show adjacency, degree, and neighborhood queries are supported in constant time.
  For any monotone class of separable graphs, the storage requirement of the encoding matches the information-theory minimum to within lower order terms. Many graphs in computational geometry that arise in practice are indeed separable. In particular, planar graphs are separable, and therefore, we achieve the first such succinct encoding for planar graphs.
  We also show how the scheme can be adapted to succinctly encode the combinatorial embedding of planar graphs (and hence encode planar maps).

• Date: Thu, 28 Oct 2010, 17:00
• Location: SR 301
• Speaker: Daniel Delling, Microsoft Research, USA
• Inhalt: We present a novel algorithm to solve the nonnegative single-source shortest path problem on road networks and other graphs with low highway dimension. After a quick preprocessing phase, we can compute all distances from a given source in the graph with essentially a linear sweep over all vertices. Because this sweep is independent of the source, we are able to reorder vertices in advance to exploit locality. Moreover, our algorithm takes advantage of features of modern CPU architectures, such as SSE and multi-core. Compared to Dijkstra's algorithm, our method makes fewer operations, has better locality, and is better able to exploit parallelism at multi-core and instruction levels. We gain additional speedup when implementing our algorithm on a GPU, where our algorithm is up to three orders of magnitude faster than Dijkstra's algorithm on a high-end CPU. This makes applications based on all-pairs shortest-paths practical for continental-sized road networks. The applications include, for example, computing graph diameter, exact arc flags, and centrality measures such as exact reaches or betweenness. Paper available at: http://research.microsoft.com/apps/pubs/default.aspx?id=138638 Joint work with Andrew Goldberg, Andreas Nowatzyk, and Renato Werneck

• Date: Tue, 26 Oct 2010, 14:00
• Location: SR 301
• Speaker: Ben Strasser, Studienarbeiter
• Inhalt: In dieser Studienarbeit geht es darum Zeitpläne für heterosexuelle und homosexuelle Speeddating Events zu erstellen. Gegeben ist eine Liste von potentiellen Dates mit Gewichten. Ziel ist es eine maximal gewichtete und faire Untermenge davon auszuwählen (match) und auf eine vorgegebene Anzahl von Zeitslots zu verteilen (schedule). Wir betrachten dabei sowohl heterosexuelle Dates als auch homosexuelle Dates. Zuerst formalisieren wir die Problemstellung als graphentheoretisches Problem. Matchings und Kantenfärbungen ergeben sich dabei als Teilprobleme. Wir beschäftigen uns anschließend mit einem auf MinCostFlow aufbauenden Polynomialzeit-Algorithmus für heterosexuelle Dates. Wir skizzieren anschließend einen Polynomialzeit-Approximationsalgorithmus für das NP-schwere homosexuelle Speeddating Problem. Abschließend evaluieren wir die Leistung einer Implementierung der vorgestellten Algorithmen.

• Date: Fri, 8 Oct 2010, 14:00
• Location: SR 301
• Speaker: Geraud Oscar Fofie Lafou

• Date: Mon, 20 Sep 2010, 11:00
• Location: TBA
• Speaker: Stephen Kobourov, University of Arizona
• Inhalt: Information visualization can be invaluable in making sense out of large data sets. However, traditional graph visualization methods often fail to capture the underlying structural information, clustering, and neighborhoods. Our algorithm for visualizing graphs as maps provides a way to overcome some of the shortcomings with the help of the geographic map metaphor. While graphs, charts, and tables often require considerable effort to comprehend, a map representation is more intuitive, as most people are very familiar with maps and even enjoy carefully examining maps. The effectiveness of the map representation algorithm is illustrated with applications in recommendation systems. Several related graph theoretical problems, including maximum differential coloring, k-Hamiltonian paths, and polygonal contact representation, will also be discussed

• Date: Fri, 10 Sep 2010, 14:00
• Location: SR 301
• Speaker: Thomas Bläsius, Studienarbeiter
• Inhalt: Gegeben ist ein planarer Graph mit Maximalgrad 4, sowie eine Flexibilitätsfunktion, die jeder Kante eine Flexibilität zuweist. Kann der Graph orthogonal und planar in die Ebene gezeichnet werden, sodass keine Kante mehr Knicke hat, als durch ihre Flexibilität vorgegeben? Wir zeigen, dass FlexDraw in Polynomialzeit gelöst werden kann, wenn jede Kante positive Flexibilität hat. Da FlexDraw die Frage nach der \beta-Einbettbarkeit (maximal \beta Knicke pro Kante) verallgemeinert, wird damit gezeigt, dass 1-Einbettbarkeit polyniomiell lösbar ist, was die Lücke zwischen der NP-schweren 0-Einbettbarkeit und der polynomiell lösbaren 2-Einbettbarkeit schließt.

• Date: Fri, 20 Aug 2010, 14:00
• Location: SR 301
• Speaker: Felix Brandt, Diplomarbeiter

• Date: Fri, 13 Aug 2010, 14:00
• Location: SR 301
• Speaker: Fabian Fuchs, Studienarbeiter

• Date: Mon, 9 Aug 2010, 14:30
• Location: SR 236
• Speaker: Marc Schmitzer, Diplomarbeiter
• Inhalt: In this work, we present and evaluate multiple approaches to compressing travel time data for time-dependent route planning in road networks. The approaches are based on principal component analysis and introduce a limited approximation error to the data. The compression achieved by the approaches is compared to that achieved by an algorithm devised by H. Imai and M. Iri which can be used for the same purpose. The first approach uses heuristics to separate the input data into subsets of similar functions which can be compressed more efficiently than the entire data set at once. It surpasses the compression achieved by the algorithm by Imai and Iri by approximately 25%. The second approach attempts to increase the similarities exploited by the former by modifying the travel time functions, but fails to further improve the results. The third approach presented merges the clustering of the input data with the compression process. With this approach, the compression is improved by a factor of two compared to the algorithm by Imai and Iri. Finally, we demonstrate that the approximation error introduced by the third approach is not overly detrimental to the performance of the Time- Dependent Contraction Hierarchies route planning algorithm.

=== Time = Space: From Searching and Sorting to Edge Clique Covering, fast algorithms which yield fast and small data structures ===

• Date: Thu, 22 Jul 2010, 14:00
• Location: SR 301
• Speaker: Jeremy Barbay, Universidad de Chile
• Inhalt: The talk will have two parts: 1. In the first part, more formal I will show some known results about the relation between time and space, such as - between searching in an ordered space and encoding integers, and - between sorting permutations and compressing them. 2. In the second part, more informal, I will hilight the search for the same kind of relationship between some Parameterized Complexity results and the compression of graphs, such as - Edge Clique Cover - Cluster Partitioning. This is a work in collaboration with Serge Gaspers.

• Date: Wed, 16 Jun 2010, 14:00
• Location: SR 301
• Speaker: Constantinos Tsirogiannis, TU Eindhoven
• Inhalt: Let $\R$ be a finite set of red point sites in $\mathbb{R}^d$ and let $\mathcal{B}$ be a set of $n$ blue point sites in $\mathbb{R}^d$. We want to establish ``safe'' connections between the red sites by deleting a minimum number of blue sites such that the region controlled by the red sites is connected. More precisely, we want to find a minimum-size subset $\mathcal{B}^- \subseteq \mathcal{B}$ such that the red cells in the Voronoi diagram of $\mathcal{R} \cup \mathcal{B} \setminus \mathcal{B}^-$ form a connected region. For $|\mathcal{R}|=2$ we present an optimal $O(n\log n)$-time algorithm for $d=2$, and an $O(n^{d-1})$-time algorithm for $d \geq 3$; we also show that the problem is 3SUM-hard for $d=3$. Furthermore, we show that the general problem, where the number of red sites is not a constant, is NP-hard.

• Date: Tue, 1 Jun 2010, 14:00
• Location: SR -108
• Speaker: Christian Vetter, Diplomarbeiter
• Inhalt: In this thesis we present a mobile routing application using the freely available OpenStreetMap data set. We take a look at the feasibility of exact mobile routing algorithms under practical conditions. While there exists a multitude of supplementing free software for OpenStreetMap data, as of yet none incorporate modern routing algorithms. Navit uses Dijkstra’s algorithm, Aosm and TrackMyJourney rely on online services for routing. We attempt to close this gap by supplying an open-source modular software suite for mobile navigation, while employing modern algorithms. This makes mobile routing applications with OpenStreetMap data practicable and might in turn result in an increase of error corrections in OpenStreetMap, which makes it even more attractive for routing purposes.

• Date: Tue, 25 May 2010, 14:00
• Location: SR 236
• Speaker: Jane Gao
• Inhalt: Let h>w>0 be two fixed integers. Let H be a random hypergraph whose hyperedges are all of cardinality h. To w-orient a hyperedge, we assign exactly w of its vertices positive signs with respect to the hyperedge, and the rest negative. A (w,k)-orientation of H consists of a w-orientation of all hyperedges of H, such that each vertex receives at most k positive signs from its incident hyperedges. In this talk, we discuss the relation between the (w,k)-orientation of hypergraphs and a general version of the off-line load balancing problem. When k is large enough, we determine the threshold of the existence of a (w,k)-orientation of a random hypergraph. The graph case, when h=2 and w=1, was solved recently by Cain, Sanders and Wormald and independently by Fernholz and Ramachandran, thereby settling a conjecture made by Karp and Saks. Motivated by a problem of cuckoo hashing, the special hypergraph case with w=k=1, was solved in three separate preprints dating from October 2009, by Frieze and Melsted, by Fountoulakis and Panagiotou, and by Dietzfelbinger, Goerdt, Mitzenmacher, Montanari, Pagh and Rink.

• Date: Fri, 21 May 2010, 14:00
• Location: SR 301
• Speaker: Simon Gog, Universität Ulm

• Date: Wed, 12 May 2010, 14:30
• Location: SR 301
• Speaker: Christian Herff, Studienarbeiter (IIT Delhi)
• Inhalt: Multicommodity Flow in general and Maximum Concurrent Flow in particular are difficult combinatorial problems that arise in various real-life scenarios as well as many research areas. Even though these problems can be stated as Linear Programs and thus be solved using Software-Suits like CPlex, the amount of variables and constraints is usually gigantic for real-life problems and grows exponential with the amount of nodes and arcs. Naturally, approximation algorithms for these problems have been proposed, some of which perform polynomial in the problemsize. Despite the fact that the approximation algorithms are much faster than the optimal solutions gained from the Linear Programs, the computation time for big instances is usually still very large. In this student research project we propose heuristics to decrease running times by an order of magnitude. This is done by incorporating ideas to reduce the impact of missroutings in the beginning of the fully polynomial approximation scheme (FPAS) designed by Garg and Koenemann.

• Date: Wed, 12 May 2010, 14:00
• Location: SR 301
• Speaker: Jan-Ole Sasse, Studienarbeiter

• Date: Tue, 11 May 2010, 14:00
• Location: SR 236
• Speaker: Tim Kieritz, Diplomarbeiter
• Inhalt: Server based route planning in road networks is now powerful enough to find quickest paths in a matter of milliseconds, even if detailed information on time-dependent travel times is taken into account. However this requires huge amounts of memory on each query server and hours of preprocessing even for a medium sized country like Germany. This is a problem since global internet companies would like to work with transcontinental networks, detailed models of intersections, and regular re-preprocessing that takes the current traffic situation into account. By giving a distributed memory parallelization of the arguably best current technique -- time-dependent contraction hierarchies, we remove these bottlenecks. For example, on a medium size network 64 processes accelerate preprocessing by a factor of 28 to 160 seconds, reduce per process memory consumption by a factor of 10.5 and increase query throughput by a factor of 25.