Research Seminar

A fast method for computing highway node hierarchies is developed. The result is very fast preprocessing at the cost of somewhat larger query times.

Within recent years, wireless sensor networks became a very popular tool for distributed monitoring of various physical and environmental conditions. Thanks to the ongoing miniaturization of the required hardware, this trend is likely to continue. In this thesis, we study the problems of scheduling and topology control in wireless networks. We consider both, networks with fixed transmission powers, and networks with freely adjustable transmission powers. For the scheduling problem, several methods for the computation of optimum schedules, as well as the computation of upper and lower bounds on the length of optimum schedules, are presented and analyzed. Additionally, various optimization possibilities are described. All methods have been implemented and are used in an experimental section to gain additional insights into the properties of wireless networks. Subsequently, the scheduling heuristics are extended to topology control algorithms. Goal of the topology control algorithms is the computation of topologies whose links are efficient to schedule. At the same time, the resulting topologies are required to conserve certain properties of the original network such as connectivity. The proposed topology control algorithms are compared to various existing algorithms using several quality measures for network topologies. A central part of this thesis is dedicated to the evaluation of constraint programming as a tool to solve scheduling problems under the physically motivated SINR model for wireless networks. For this purpose, constraint programming is compared to integer linear programming and several experiments are performed to highlight the pros and cons of both approaches. All constraint programs have been solved using the freely available Gecode solver which is described to some detail in the beginning of this thesis.

Phrase searches are an important operation on text search engines. This talk shows how inverted index based text search engines can be improved to achieve reduced reponse times for phrase queries.

Die betrachteten Stabilisatorgruppen sind Untergruppen von Aut(Fz) von endlichem Index, zu denen bisher nur sehr wenig bekannt ist. Sie können beispielsweise verwendet werden, um die Veechgruppe einer Überlagerung einer primitiven Translationsfläche zu bestimmen. Ziel des Vortrags ist die Vorstellung eines effizienten Algorithmus zur Berechnung des Stabilisators einer Untergruppe der freien Gruppe, sowie die Betrachtung heuristischer Maßnahmen zur Laufzeitverbesserung.

Rainbow Sort is an unconventional method for sorting, which is based on the physical concepts of refraction and dispersion. It is inspired by the observation that light that traverses a prism is sorted by wavelength. At first sight this "rainbow effect" that appears in nature has nothing to do with a computation in the classical sense, still it can be used to design a sorting method that has the potential of running in O(n) with a space complexity of O(n), where n denotes the number of elements that are sorted.

This talk will describe fast algorithms for computing exact point-to-point shortest paths (driving directions) on road networks. Our approach is a combination of two techniques: reach-based pruning eliminates local intersections, while landmark-based A* search directs the search towards the goal. On the road networks of the USA and Western Europe, an average query visits no more than a thousand road intersections (out of roughly 20 million), which is four orders of magnitude better than Dijkstra's algorithm. Besides presenting an overview of the basic techniques, the talk will discuss a few recent developments, such as an improved algorithm for computing landmarks. Joint work with Andrew Goldberg and Haim Kaplan.

Large-scale web search engines typically split the overall index into hundreds of subindices. Thus, not only different queries can be run in parallel on different servers but also the work required to answer a single query can be split across multiple servers. For high resource utilization and throughput the overall workload has to be balanced over the available servers. Experiments with query logs from AltaVista and AllTheWeb and 20M web pages from Stanford's WebBase suggest that (a) the overall load is roughly balanced over the subindices and that (b) the load generated by individual queries is rather tiny. Based on these insights we present a refined theoretical framework and devise several highly competitive loadbalancing strategies.

We present a route planning technique solely based on the concept of node contraction. The nodes are first ordered by 'importance'. A hierarchy is then generated by iteratively contracting the least important node. Contracting a node v means replacing shortest paths going through v by shortcuts. We obtain a hierarchical query algorithm using bidirectional shortest-path search. The forward search uses only edges leading to more important nodes and the backward search uses only edges coming from more important nodes. For fastest routes in road networks, the graph remains very sparse throughout the contraction process using rather simple heuristics for ordering the nodes. We have five times lower query times than the best previous hierarchical Dijkstra-based speedup techniques and a negative space overhead, i.e., the data structure for distance computation needs less space than the input graph. CHs can be combined with many other route planning techniques, leading to improved performance for many-to-many routing, transit-node routing, goal-directed routing or mobile and dynamic scenarios.

Highway-Node Routing is a scheme for solving the shortest path problem showing excellent speedups. There also is a dynamic variant that allows changes to the cost function. Based on an existing, sequential implementation of this precomputation, we present a parallel version. We also present experimental results with the road network of Europe as the input.
During the parallelization, problems with imbalanced load and memory bandwidth limitations were encountered. We evaluated several load balancing variants and also a modification that makes the problem more regular. We also considered a scheme that tries to exploit the shared cache structure of the used machine to lessen the memory bandwidth limitation. When making the problem more regular, the best variant achieves a speedup of 7.0 with 8 threads with no significant effect on query time. When the result is to be identical to the sequential version's, the best variant achieves a speedup of 5.9 with 8 threads.

Estimating the importance or centrality of the nodes in large networks has recently attracted increased interest. Betweenness is one of the most important centrality indices, which basically counts the number of shortest paths going through a node. Betweenness has been used in diverse applications, e.g., social network analysis or route planning. Since exact computation is prohibitive for large networks, approximation algorithms are important. In this paper, we propose a framework for unbiased approximation of betweenness that generalizes a previous approach by Brandes. Our best new schemes yield significantly better approximation than before for many real world inputs. In particular, we also get good approximations for the betweenness of unimportant nodes.

Der Cross-Match-Test ist ein nichtparametrischer Zweistichprobentest, der sich eines minimalen, perfekten Matchings bedient um eine geeignete Teststatistik zu definieren. Ziel der Studienarbeit war es zu untersuchen, ob neben dem exakten Matchingalgorithmus von Edmonds auch nicht exakte, dafür aber schnellere und einfacher zu implementierende Algorithmen für die Anwendung innerhalb des Cross-Match-Tests geeignet sind. Die experimentelle Untersuchung beschränkte sich dabei auf den Algorithmus nach Wattenhofer und Wattenhofer als Beispiel approximativer Matchingalgorithmen.

In diesem Vortrag wird der k-Betweenness-Algorithmus, eine Variante des Newman-Girvan-Algorithmus, präsentiert. Im Anschluss soll das Verhalten von diesem sowie die empirischen Ergebnisse zu Laufzeitverbesserung und Qualitätseinbußen bei verschiedener Parameterauswahl vorgestellt werden.

Web search engines answer hundreds of millions of queries per day. Answering one user query requires a short amount of processing on thousands of machines. For fast query processing it is important to efficiently balance the load over the involved machines. Interestingly, this load has several properties that are not captured by existing load-balancing models. We present and analyze a refined model that takes these characteristics into account.

Es gibt eine Reihe von unteren Schranken für die Kardinalität von größten Matchings in gewissen Graphenklassen. Beispielsweise besitzt jeder 3-reguläre Graph ein Matching der Größe (4n-1)/9. Die Arbeit beschäftigt sich mit der Fragestellung, ob Matchings dieser Mindestgröße (von denen man ja weiß, dass sie existieren) schneller gefunden werden können als durch Berechnung eines größten Matchings.

Planare Graphen werden häufig geradlinig auf einem ganzzahligen Gitter gezeichnet. Durch die Geradlinigkeit der Kanten lassen sich die Graphen vom Betrachter leicht erfassen. Darüber hinaus vermeidet man durch ganzzahlige Arithmetik, dass die Planarität der Zeichnung beim Runden der Koordinaten zerstört wird. Generell ist man unter anderem an Zeichnungen mit geringem Flächenbedarf interessiert. Ziel des Vortrags ist es zu zeigen, dass es NP-schwer ist zu entscheiden, ob ein planarer Graph auf einem Gitter mit vorgegebenem Flächenbedarf gezeichnet werden kann.

Ziel dieser Arbeit ist es zu untersuchen, inwieweit sich der Algorithmus von Stoer und Wagner dazu verwenden lässt, einen minimalen Schnittbaum zu erzeugen. Der Algorithmus von Stoer und Wagner berechnet den minimalen Schnitt in einem Graphen und erzeugt im Laufe dessen insgesamt n − 1 unterschiedliche Schnitte des Graphen. Eine genauere Untersuchung dieser Schnitte ergab leider, dass sie sich nicht dazu eignen, einen minimalen Schnittbaum zu erstellen. Sie sind zwar linear unabhängig und erfüllen die notwendigen Eigenschaften, dass sie sich paarweise nicht kreuzen, das Gewicht des aus ihnen berechneten Schnittbaumes ist aber nicht minimal. Auch als Heuristik erzielt der Algorithmus keine guten Resultate.
Als zweiten Teil der Arbeit wurden Heuristiken zu Schnittbäumen untersucht. Die Heuristiken des maximalen kurzen Baumes und des daraus resultierenden optimierten Baumes laufen schnell und zuverlässig auf den getesteten Graphen. Eine Gütegarantie mit Faktor 2 sichert konstant gute Ergebnisse.

Bei Cross-Match-Tests handelt es sich um nichtparametrische, multivariate Zwei-Stichproben-Verteilungstests, deren Teststatistik auf minimal gewichteten Matchings basiert. Desto ähnlicher die Verteilungen der zugrundeliegenden Stichproben, desto mehr Cross-Matches zwischen den beiden Stichproben erwartet man. Angesichts der Laufzeit des exakten Matchingalgorithmus von Edmonds (1965) soll nun untersucht werden, in wie weit die Verwendung schnellerer Approximationsalgorithmen das Verhalten der Teststatistik verändert.

Modern software design relies on the interaction and extension of well-defined, robust and flexible predefines software components. Data structures libraries define interfaces and implement fundamental data structures and algorithms. Nowadays, they are included as part of most programming languages and so, they are very accessible. As an specific case, we focus on the C++ Standard Library, and more in particular, on the Standard Template Library(STL). On the other hand, in the last years there have been great advances in the algorithmic communit and hardware: managing large volumes of data, taking advantage of the cache hierarchy, multicore computers... But data structures libraries do not take much advantage of this work. Indeed, the requirements or assumptions are oftenly quite different. But anyway, they are using the same abstractions.
The goal of my thesis is enhancing some STL components with up-to-date knowledge on algorithms and data structures while keeping with STL requirements. In this talk, I will present briefly specific problems I have been dealing with.

As the Internet develops, the simulation of the Internet becomes an urgent request nowadays. To obtain an accurate simulation, we need to model the Internet topology. The modeling of the Internet topology started a from random model to the hierarchical model and then it developed to a scale-free network model. Many characteristics of topology have been analyzed with the corresponding metrics, including the prominent Power-Law distribution (eg. frequency, degree). Modeling the Internet topology is still an important open problem, since an accurate topological model can have significant impact on network research. In this paper we discuss some popular Internet topology models and several relevant Internet topology generators at the autonomous system (AS) level, one of which has been developed at our institute.

Viele Routing-Algorithmen die energieminimale Wege suchen, berücksichtigen nicht, dass Verbindungen unzuverlässig sein können und so zusätzliche Energie aufgewendet wird, wenn die Übertragung wiederholt werden muss. In einem Artikel von Dong, Banerjee, Adler und Misra wurde nun ein Modell entworfen, das dies zu berücksichtigen versucht und Algorithmen besprochen, die in diesem Modell energieminimale Wege finden.

We study the point-to-point shortest path problem in a setting where preprocessing is allowed. We improve the reach-based approach of Gutman in several ways. In particular, we add shortcut arcs which reduce vertex reaches. Our modifications greatly reduce both preprocessing and query times. Our algorithm combines in a natural way with A* search, which yields significantly better query times and allows a wide range of time-space trade-offs. The resulting algorithms are quite practical for our motivating application, computing driving directions, both for server and for portable device applications.

A Cover Contact Graph (CCG) is a graph defined by a pair G=(S,C), where S is a set of objects (called seeds) in the plane, and C is a collection of discs or triangles (called covers) covering the seeds, with the property that the interior of those discs or triangles are mutually disjoint. The contact graph of C is a CCG. We study three basic properties of CCG's taking into account the nature of the seeds and of the covers. Namely, whether there exists a connected CCG on a fixed seed set, whether is it possible to realize a given graph as a CCG, and finally we try to enumerate certain classes of CCG's. Different results about these three basic problems were presented at the 22nd European Workshop on Computational Geometry [1]. Here we will focus on some representative results concerning connectivity, realization or enumeration problems.

In diesem Abschlussvortrag zur Diplomarbeit werden dynamische Varianten bekannter Beschleunigungstechniken für den Dijkstra-Algorithmus vorgestellt werden, besonders der Multilevel- und der Reach-Technik.

In der Kartographie versteht man unter dem Begriff Generalisierung die Aufgabe, einen kleineren Maßstab aus einer bestehenden Repräsentation abzuleiten. Hierbei sind verschiedene Teilprobleme wie Vereinfachung, Aggregation, Selektion und Typifizierung zu lösen. Einige dieser Probleme konnten in der Vergangenheit für bestimmte Objektklassen erfolgreich automatisiert werden. Generell ist allerdings weitere Forschung notwendig. Neben der Diskussion anderer Probleme wird insbesondere ein neues Verfahren zur Aggregation von Flächen präsentiert, welches für die Generalisierung von Landnutzungskarten entwickelt wurde. Der Information über Landnutzung wird eine große Bedeutung beigemessen, da sie eine wichtige Grundlage für topographische Karten darstellt. Abschließend werden einige neue Herausforderungen besprochen, die sich aus aktuellen Entwicklungen in der Geoinformatik ergeben. Hierbei ist insbesondere das Problem der inkrementellen Generalisierung zu nennen, zu dem Lösungsansätze aufgezeigt werden.

In dieser Studienarbeit wird untersucht, mit welchen Methoden sehr große Graphen wie ein Straßennetzwerk von Europa effizient und komfortabel visualisiert werden können. Als Ausarbeitung entsteht ein C++ Rahmenwerk für die Datenhaltung eines Graphen mit Attributen und ein Java Applet, das mit dem Datenhaltungs-Server mittels CORBA kommuniziert. Das Rahmenwerk kann leicht in bestehende Graphanwendungen integriert werden, um deren Algorithmen zu animieren.
Um die Geschwindigkeit einer Ausschnittsanfrage zu erhöhen, wird die mehrdimensionale Indexstruktur R-Tree verwendet. Diese ermöglicht Anfragezeiten, die linear zur Anzahl der zurückgelieferten Kanten und unabhängig vom gewählten Ausschnitt sind. Es können komplexe Filterausdrücke aus Vergleichsbedingungen mit boolschen und arithmetische Operatoren verwendet werden, um die angezeigten Kanten in einem Visualisierungsauschnitt einzuschränken und so komfortabel bestimmte Aspekte der Anwendungs-Algorithmen zu untersuchen oder hervorzuheben.

Data representing moving objects is rapidly getting more available, especially in the area of wildlife GPS tracking. It is a central belief that information is hidden in large data sets in the form of interesting patterns. One of the most common spatio-temporal patterns sought after is flocks. A flock is a large enough subset of objects moving along paths close to each other for a certain pre-defined time. We give a new definition that we argue is more realistic than the previous ones, and we present fast approximation algorithms to report flocks. The algorithms are analysed both theoretically and experimentally.

1977 veröffentlichten K. Appel und W. Haken ihren berühmten Beweis zu der seit 100 Jahren offenen 4-Farben-Vermutung. Diese besagt, dass jeder planare Graph eine Knotenfärbung mit höchstens 4 Farben zulässt. Der Beweis von Appel und Haken war zunächst umstritten, vor allem deshalb, weil er Computer benutzt um gewisse Fallunterscheidungen durchzuführen. Zwanzig Jahre später veröffentlichten N. Robertson, D. Sanders und R. Thomas einen neuen, einfacheren Beweis, der aber immer noch die Hilfe von Computern erfordert. Die Autoren geben in dieser Arbeit auch einen Algorithmus an, der in quadratischer Zeit eine solche 4-Färbung berechnet.
In meinem Vortrag werde ich zunächst einen kurzen Überblick zur Struktur des Beweises geben. Hauptsächlich geht es jedoch darum, über eine mögliche Verbesserung des eigentlichen Algorithmus zur Vierfärbung von quadratischer Zeit zu Linearzeit zu spekulieren.

Der Heapsort-Algorithmus gilt als eines der am schwierigsten zu verifizierenden Sortierverfahren. Der Vortrag stellt die grundlegenden Algorithmen zur Behandlung von Heaps dar.
Im Unterschied zu den anderen Vorträgen dauert der Vortrag 40 Minuten. In der ersten Hälfte wird exemplarisch erlaeutert, wie Programme spezifiziert und verifiziert werden.

In dieser Arbeit wird eine Erweiterung des Multi-Level-Ansatzes [1] zur exakten Bestimmung kürzester Wege vorgestellt. Der Eingabegraph wird in einer Vorberechnungsphase in eine Komponentenhierarchie zerlegt, aus der Hilfsdaten generiert werden. Die Hilfsdaten bestehen hier aus vielen kleinen Graphen, aus denen für jede Distanz-Anfrage leicht ein Suchraum-Graph kombiniert werden kann, in dem die Distanz zwischen zwei dedizierten Knoten der angefragten Distanz entspricht. Da der Suchraum-Graph sehr klein im Vergleich zum Eingabegraphen ist, geht die eigentliche Suche sehr schnell vonstatten.
Die Dauer einer Suchanfrage kann garantiert werden, diese hängt vom Umfang der Hilfsdaten und von der Dauer der Vorberechnung ab. Die Vorberechnung selbst ist gut parallelisierbar. Die Hilfsdaten können im Externspeicher verwaltet werden, in diesem Fall werden pro Anfrage nur wenige Zugriffe auf den Externspeicher benötigt. Wenn die Hilfsdaten im Arbeitsspeicher abgelegt werden, ist die Anfragezeit für große Straßen-Netzwerke mit anderen aktuellen Ansätzen [2, 3] vergleichbar.

[1] Martin Holzer, Frank Schulz, and Dorothea Wagner. Engineering multi-level overlay graphs for shortest-path queries.
[2] Peter Sanders and Dominik Schultes. Highway hierarchies hasten exact shortest path queries.
[3] Andrew Goldberg, Haim Kaplan, and Renato Werneck. Reach for A*: Efficient point-to-point shortest path algorithms.

In this research work, we propose to address issues of discovery, composition and mediation of services and more specifically of Web services. The composition and discovery process is a challenging task because Web services are expected to be numerous, autonomous and heterogeneous. We model the problem as a forward shortest path problem in a hypergraph and we adopted solutions developed in the context of AI search for computation of forward shortest hyperpaths in hypergraphs, which is a NP-complete problem. The research proposes three algorithms based on Dijkstra’s, A* and forward chaining algorithm for automatic optimal or near –optimal composition of Web services. These algorithms are implemented in C. The empirical performance of the proposed algorithms and their variants are comparatively evaluated.

A generalized paging problem is considered. Each request is expressed as a set of u pages. In order to satisfy the request, at least one of these pages must be in the cache. Therefore, on a page fault, the algorithm must load into the cache at least one page out of the u pages given in the request. The problem arises in systems in which requests can be serviced by various utilities (e.g., a request for a data that lies in various web-pages) and a single utility can service many requests (e.g., a web-page containing various data). The server has the freedom to select the utility that will service the next request and hopefully additional requests in the future. The case u=1 is simply the classical paging problem, which is known to be polynomially solvable. We show that for any u>1 the offline problem is NP-hard and hard to approximate if the cache size k is part of the input, but solvable in polynomial time for constant values of k. We consider mainly online algorithms, and design competitive algorithms for arbitrary values of k,u. We study in more detail the cases where u and k are small. We also give an algorithm which uses resource augmentation and which is asymptotically optimal for u=2.

We propose a drawing convention for micro/macro graphs, i.e.relational structures at two levels of detail. Prototypical examples for macro-level structures are quotient graphs, which result from contracting sets of vertices in a given (micro-level) graph. While the coarse macro graph can be laid out in any style fit, its elements are rendered with sufficient thickness to draw the underlying micro graph on top of them, so that the contribution of micro-level elements to macro-level structure becomes apparent. Moreover, a concrete instantiation of micro-graph layout based on a circular layout technique is given.

At ESA 2005, we presented a shortest path algorithm that allows fast point-to-point queries in graphs using preprocessed data. Here, we give an extensive revision of our method. It allows faster query and preprocessing times, it reduces the size of the data obtained during the preprocessing and it deals with directed graphs. Preprocessing the network of Western Europe, which consists of about 18 million nodes, takes 21 minutes and yields 66 bytes of additional data per node. Then, random queries take 1.94 ms on average.

STXXL is a library of basic I/O-efficient algorithms and data structures. It has interfaces of the standard C++ library STL, but can handle efficiently huge inputs that do not fit into internal memory of a computer. The library supports disk parallelism, pipelining of algorithms to save I/Os, overlapping between I/O and internal computation. We discuss algorithmic ideas of recent I/O-efficient graph algorithms for computing breadth first search level decompositions, minimum spanning forests and graph coloring, and present their STXXL implementations. We demonstrate that very large instances of these problems, taking up to hundreds of gigabytes just to represent the input, can be solved within few hours on a low-cost hardware.

Clique enumeration is an important task in computer science. By the recent rapid growth of databases, automatic processing using cliques is getting more important. Thanks to the progress of computational power and database technologies, we can enumerate cliques of large graphs in time short enough in a practical sense. Now we are going to the next step. In practice, what we really want to find is clique-like structures, i.e. vertex sets having many edges in their induced subgraphs. Our motivation is that real world data may include some error, missing edges, and incompleteness. Cliques are a special case in which we can solve the problems easily. In this talk we address the problem of enumerating vertex sets having many edges in their induced subgraphs. We

prove that straightforward approaches may not work,
propose a polynomial time algorithm, and
show results of computational experiments.

We present an optimal broadcast algorithm for fully connected networks under a linear communication cost model in which each processor can simultaneously send a message to one processor and receive a message from another. For any number of processors

the number of communication rounds required to broadcast

blocks of data is $N-1+\lceil \log p\rceil$ . For data of size

, assuming that sending and receiving

data units takes time $\alpha+\beta m$ , the best running time that can be achieved is $(\sqrt{(\lceil \log p\rceil -1)\alpha}+\sqrt{\beta m})^2$ . The algorithm has a regular communication pattern based on arc disjoint binomial trees, and has a binomial tree broadcast as a special case when the number of blocks to be broadcast is one. The same algorithm can therefore be used for all message sizes

, and is furthermore well-suited for SMP clusters. We demonstrate significant practical improvements of up to a factor 1.5 over several other, commonly used broadcast algorithms.

This student research project studies a variant of the load balancing problem with restricted assignments and permanent tasks which arises in web search engines. We show that for our variant of the problem the greedy scheduling algorithm achieves maximum machine load within a constant factor of the optimum. This result substantiates the popularity of the greedy algorithm amongst software engineers for balancing load among multiple machines and gives an interesting contrast to the result by Azar et al. showing that the competitive ratio of the greedy algorithm with restricted assignment and permanent tasks is Θ(log m), where m is the number of machines.

Geovisualisierung ist ein aktuelles interdisziplinäres Forschungsgebiet, das sich mit der visuellen Exploration, Analyse, Synthese und Präsentation von räumlichen Daten beschäftigt. Neben den klassischen von Kartographen erzeugten Landkarten gibt es eine Fülle von interaktiven und dynamischen Methoden aus dem Bereich der Informationsvisualisierung, die auch zur Visualisierung von geographischen Daten benutzt werden können. Allerdings erfordern geographische Daten oft besondere Darstellungsformen. In diesem Vortrag werden mehrere Visualisierungstechniken vorgestellt, allerdings mit einem besonderen Fokus auf die Bedürfnisse menschlicher Benutzer und die Benutzbarkeit von Geovisualisierungssystemen.

I will present a polynomial-time approximation algorithm for labeling weighted points with horizontally sliding labels of unit height and given lengths. The aim is to maximize the total weight of the labeled points. The approach is based on a discretization, and two results are established: In general, the algorithm has an approximation factor of (2/3-epsilon), for arbitrary fixed epsilon>0. If the ratio of maximal to minimal label lengths is bounded by a constant, the approximation factor becomes (1-epsilon).

We extend a dynamic-programming algorithm of Keil and Snoeyink for finding a minimum convex decomposition of a simple polygon to the case when both con- vex polygons and pseudo-triangles are allowed. Our algorithm determines a minimum pseudo-convex decomposition of a simple polygon in O(n³) time where n is the number of the vertices of the polygon. In this way we obtain a well-structured decomposition with fewer polygons, especially if the original polygon has long chains of concave vertices.

Ein Ansatz zum Vergleichen von Clusterungen sind Abstandsmaße, die einen Wert von Null für zwei gleiche und von Eins für zwei maximal verschiedene Clusterungen berechnen. Ziel der Diplomarbeit war die systematische Analyse der bisherigen Maße. Dabei stellte sich heraus, dass bisherige Maße für die Abstandsmessung lediglich die Knotenmenge benutzen, was auch für den Fall, dass beide Clusterungen auf dem gleichen Graphen definiert sind, ein großer Nachteil ist. Ferner stellte sicher heraus, dass auf Clusterungen drei Arten von Abstand denkbar sind.
Thema des Vortrags sind die Gliederung der Abstandsarten, die Nachteile bisheriger Maße, Erweiterungen dieser Maße, damit sie eine andere Abstandsart messen, und die Ergebnisse einiger Testreihen.

Modularity ist ein Bewertungsmaß für (Graph-)Clusterungen, welches von Physikern erfunden wurde. Entsprechende waren lange einige Fragen offen, wie zum Beispiel die Berechenbarkeit oder das Verhältnis der Intuition zur Formalisierung. Inzwischen konnte gezeigt werden, dass das Entscheidungsproblem NP-vollständig ist. Im Vortrag soll nun gezeigt werden, welche Clusterintuitionen in dem Maß stecken und wie sich das Problem auf eingeschränkten Klassen (vollständige Graphen und einfache Kreise) optimal lösen lässt.

Klassische Formulierungen des Planar-Separator-Theorems wie die von Lipton und Tarjan lassen einer konkreten Implementierung etliche Freiheitsgrade u. a. hinsichtlich BFS-Wurzel-Auswahl und Wahl einer Nichtbaumkante, deren Einfluss auf die Separatorqualität kürzlich untersucht wurde und sich dabei als signifikant herausgestellt hat. Im Rahmen einer Studienarbeit wurden weitere Freiheitsgrade des PST, die bei der Konstruktion eines aufspannenden Baumes bzw. einer Triangulierung auftreten, evaluiert und zahlreiche Optimierungsansätze vorgestellt. Experimente konnten eine weitere deutliche Verbesserung der praktischen Performanz im Vergleich zu naiven Implementationen aufzeigen.

Bei der Rekonstruktion der Topologie von Sensornetzen wird üblicherweise auf Entfernungsmessungen zurückgegriffen. Selbst vorhandene Algorithmen zur Richtungsgestützten Lokalisierung nutzen die Vorzüge nicht konsequent aus und bauen damit immer noch wesentlich auf das Lösen Linearer Programme. Diese Arbeit beschäftigt sich zum einen mit dem schnellen Auffinden und Auslegen maximaler eindeutig rekonstruierbarer Subgraphen, um das entsprechende Lineare Programm so weit wie möglich zu vereinfachen, und zum anderen mit einer Variante dieses Vorgehens zur Rekonstruktion auch bei fehlerbehafteten Messungen.

We consider the problem of placing a set of discs in a region containing obstacles such that no two discs intersect. We are given a bounding polygon P and a set R of possibly intersecting unit disks whose centers are in P. The task is to find a set B of unit disks such that no disc in B intersects a disc in B u R. Finding a set B containing the maximum possible number m of unit disks is known to be NP-hard.
We consider the variant of the problem, where the aim is to pack m non-intersecting discs of maximum radius, where m is as defined above. The problem has applications in computer graphics and GIS. In this paper we present a 2/3-approximation algorithm.

Suffix-Tabellen sind in den letzten Jahren zu einem wichtigen Instrument zur Suche in Zeichenfolgen geworden. Ohne Vorverarbeitung von Zeichenfolgen ist die benötigte Zeit zur Suche nach einem bestimmten Muster im Allgemeinen linear zur Länge der Zeichenfolge. Mit Hilfe der Suffix-Tabelle kann das Muster in logarithmischer Zeit gefunden werden. Um die benötigte Zeit zur Konstruktion der Suffix-Tabellen zu reduzieren, kann man bereits vorhandene Algorithmen auf immer schnelleren Rechnern ausführen. Diesem Vorgehen sind aber enge technische Grenzen gesetzt.
Eine Alternative dazu ist die parallele Konstruktion von Suffix-Tabellen. In diesem Vortrag soll die Leistungsfähigkeit einer skalierbaren Implementierung eines parallelen Algorithmus anhand von Messungen präsentiert werden.

Heutzutage verwendete Textkompressions-Verfahren beschränken die Adaption des Modells zu jedem Zeitpunkt auf einen Teil der Eingabe. Diese Selbstbeschränkung ist jedoch nicht mehr zeitgemäß, da Hauptspeicher und Rechenleistung in großen Mengen zur Verfügung stehen. In dieser Diplomarbeit wird untersucht, ob und in welchem Ausmaß die Kompressionsrate dadurch gesteigert werden kann, dass die Eingabe zunächst komplett analysiert wird, also global vorgegangen wird. Dazu werden erstens etablierte Kompressionsverfahren unter dieser neuen Rahmenbedingung studiert und modifiziert. Zweitens wird ein eigenes Verfahren vorgeschlagen, implementiert und experimentell mit etablierten Kompressoren verglichen. Dieses neue Verfahren verwendet die Datenstruktur eines Suffix-Array, um Wiederholungen gleicher Teilstücke im Text zu finden und diese durch eine Referenz auf ein bestimmtes Vorkommen zu ersetzen. Es kann Texte eigenständig komprimieren oder als Vorstufe für andere Kompressionsverfahren nutzen. Es wird aufgezeigt, dass der globale Ansatz für einige Fälle, vor allem große Dateien, eine Verbesserung der Kompressionsrate ermöglicht.

Zur Analyse von Literatur-, Kollaborations- oder Kozitationsnetzwerken ist oftmals mühsames Parsen von Datendumps notwendig. Gefolgt wird dies zumeist von Dingen wie manueller Säuberung, Beschränkung auf gewisse Kantengewichte, oder der Suche nach der Nachbarschaft gegebener Knoten. Es wird ein Werkzeug vorgsestellt, welches auf der Basis eines XML-Parsers und einer Datenbank aus Datendumps Graphen extrahiert. Dabei bietet das Yed-Interface viele bequeme Features zur Gestaltung des gesuchten Graphen. Bislang werden als Datenquellen Citeseer und DBLP unterstützt.

Many recent approaches for the source-target shortest path problem in road networks are based on Dijkstra's algorithm, e. g. ALT/REACH, Highway Hierarchies, Geometric Containers, A* goal-directed search etc. Most of them use precomputation to restrict the choice of the edges considered during search, but the search is still performed on the whole map -- which can be huge.
Precomputation of all paths would allow to determine any single path in time dependent only on path length. But for huge road maps, running a simple all-pairs shortest path search would take far too long and use too much space to be useful. In 1998, Ning Jing et al. introduced a scheme for efficient APSP precomputation, storage and update, based on multi-level hierarchies. With this scheme a source-target shortest path search between any two points - no matter how far they are from each other - can be mapped to execution of a variant of Dijkstra's algorithm on a small graph and subsequent lookup of the path's course.
The aim of this talk is to present an evaluation of this scheme and to show possible research topics.

Ein Ansatz, um zwei Clusterungen miteinander zu vergleichen und festzustellen wie verschieden bzw. ähnlich sie sind, ist der Gebrauch von Vergleichsmaßen. Wann ein Vergleichsmaß z.B. einen kleinen Abstand zweier Clusterungen ausweisen soll, kann aber von Anwendungsfall zu Anwendungsfall stark variieren. Daher ist es sinnvoll, zunächst mögliche Intuitionen für Abstände und Gleichheit zweier Clusterungen zu sammeln und zu formalisieren und aus diesen Intuitionen Regeln für Vergleichsmaße abzuleiten, um dann mögliche Vergleichsmaße zu definieren. Vorgestellt wird unsere Einteilung der Intuitionen, welcher Intuition bisherige Vergleichsmaße entsprechen und wie man diese Maße erweitern kann, damit sie andere Intuitionen repräsentieren. Desweiteren stellen wir einen neues Vergleichsmaß und erste Ergebnisse vor.

Graphpartitionierung ist ein bekanntes NP-vollständiges Problem, das beispielsweise bei der Parallelisierung von gitterbasierten Simulationsmethoden oder für die Beschleunigung von Shortest-Path Algorithmen wichtige Anwendungen hat. Insbesondere beschäftigen wir uns mit der Partitionierung von Graphen mit Millionen von Knoten in tausende oder zehntausende von Stücken. Wir entwickeln einen geometrischen Partitionierungsalgorithmus, der weit bessere Ergebnisse als das klassische Recursive Coordinate Bisection Verfahren liefert. In vielen Fällen liegt der Kantenschnitt nur um 45% über dem des Multilevel-Partitionierers METIS, während die Laufzeit in Bezug auf die Anzahl der Partitionen weit besser skaliert. Weiterhin untersuchen wir METIS im Hinblick auf Effizienz und Skalierbarkeit und schlagen mehrere Verbesserungen vor.

Drahtlose Sensornetze sind relativ störungsanfällig. Deshalb kann es sinnvoll sein, Informationen über mehrere disjunkte Wege von einem Sender zu einem Empfänger zu senden, um die Redundanz zu erhöhen. Andererseits spielen Energiebetrachtungen in drathlosen Sensornetzen eine wichtige Rolle. Die disjunkten Wege sollen deshalb möglichst energieeffizient sein. In diesem Vortrag sollen Ergebnisse zur Komplexität und Heuristiken auf allgemeinen und speziellen Graphen vorgestellt werden.

Eine konvexe Zerlegung eines einfachen Polygons P ist eine Überdeckung von P mit konvexen, paarweise disjunkten Polygonen, die innerhalb von P liegen und deren Ecken Ecken von P sind. Man kann ein einfaches Polygon immer konvex zerlegen, indem man das Polygon trianguliert. Das Problem besteht jedoch darin, eine Zerlegung zu finden, die möglichst wenige konvexe Polygone benutzt. Im Seminar wird über einen Algorithmus von Keil und Snoeyink berichtet, der das Problem optimal löst.

Zu den grundlegendsten Aufgaben in Sensornetzwerken gehört die Lokalisierung der Knoten; sie ist natürlich notwendig für eine Auswertung der Daten, aber auch für geometrische Routing-Verfahren. In den meisten bisher vorgestellten Ansätzen werden neben der Modellierung als Quasi Unit Disc Graphs (QUDG) Informationen über die Entfernung miteinander kommunizierender Knoten verwendet. Obwohl technisch aufwendiger zu erlangen, ist die Kenntnis der Winkel im eingebetteten Kommunikationsgraphen der Kenntnis der Kantenlängen überlegen. Sie ermöglicht eindeutige Lokalisierung unter geringeren Voraussetzungen und effiziente Verfahren zur konsistenten Einbettung auch bei Mehrdeutigkeiten. Vorgestellt werden weiterhin Überlegungen zur Ausnutzung von Redundanz bei fehlerbehafteten Winkelmessungen.

Die Hauptaufgabe des Internets ist die Weiterleitung von Datenpaketen. Für die Bestimmung der Route der Datenpakete von der Quelle zur Senke ist das Routing im Internet verantwortlich. Hierbei ist die Stabilität der Routen ein sehr wichtiger Aspekt, da jeder Routenwechsel Paketverluste hervorruft und dadurch die Ende-zu-Ende-Verbindung stört.
Das Fast Scoped Rerouting-Verfahren hat zum Ziel die Routen des Internets zu stabilisieren, im Fehlerfall schnell eine alternative Route bereitzustellen und Auswirkungen von Fehlern zwischen Autonomen Systemen zu begrenzen. Für kurzzeitige Ausfälle/Fehler etabliert das FaSRo-Verfahren eine Umleitung und begrenzt damit die Anzahl der Routing-Kontrollnachrichten. Hierdurch wird eine Dämpfung der Routenänderungsdynamik erreicht.

Clustergraphen sind Graphen, für deren Knotenmenge eine hierarchische Partitionierung gegeben ist. Ziel einer planaren Zeichnung eines Clustergraphen ist nicht nur eine planare Zeichnung des zugrundeliegenden Graphen, sondern auch die Planarität der einzelnen Clusterregionen untereinander. Bisherige und neue Resultate zu Planaritätstests von Clustergraphen werden vorgestellt.

Min-wise Independent Permutations können zur effizienten Implementierung von Streaming Algorithmen eingesetzt werden. In meinem Vortrag beschreibe ich eine entsprechende Programmbibliothek und deren Optimierung sowie erste Resultate und Probleme bei deren Einsatz in einem Algorithmus zur approximativen Bestimmung der Häufigkeit von Elementen in einem Data-Stream.

Mithilfe eines auf dem Spring Embedder Layout eines Graphen beruhenden Dimensionsbegriffs wird ein empirischer Vergleich zwischen spektralen und kräftebasierten Layouts in geeigneten Räumen durchgeführt. Im Vortrag sollen die Grundlagen eines solchen Vergleichs dargelegt und die bisherigen Ergebnisse diskutiert werden.

Im Straßenverkehr wird die Bewegungsfreiheit häufig durch Abbiegeverbote eingeschränkt. Diese Arbeit untersucht, wie Kürzeste-Wege-Algorithmen erweitert werden können, so dass zwischen zwei Knoten der kürzeste Weg gefunden wird, der alle Abbiegeverbote berücksichtigt.

Für einen planaren Graphen wird eine Einbettung derart gesucht, dass die Distanz zur Außenfacette minimiert wird. Hierbei seien zwei Facetten adjazent, wenn sie einen Knoten gemeinsam haben, und das Problem ist polynomiell lösbar. Dieses Problem ist mit einem anderen verwandt, nämlich der Triangulierung von planaren Graphen mit minimalem Radius oder Durchmesser.

Es wird der Beweis von Jack Snoeying vorgestellt, der es geschafft hat, die Termination unseres Recoloring-Algorithmus für unscharfe Regionen zu zeigen.

In praktischen Anwendungen des Planar-Separator-Theorems (PST) sollen oft nicht nur die gegebenen Schranken an Separatorgröße bzw. Balanciertheit eingehalten, sondern diese beiden Größen optimiert werden. Klassische PST-Formulierungen lassen der Implementierung jedoch etliche Freiheitsgrade u. a. hinsichtlich BFS-Wurzel-Auswahl und Wahl einer Nichtbaumkante, deren Einfluss auf die Separatorqualität kürzlich untersucht wurde und sich dabei als signifikant herausgestellt hat.
Im Rahmen einer Studienarbeit sollen weitere Freiheitsgrade des PST, die bei der Konstruktion eines aufspannenden Baumes bzw. einer Triangulierung auftreten, evaluiert werden. Erste Ideen dazu sollen nun in diesem Vortrag vorgestellt werden.

In recent years, the development of theoretically I/O-efficient algorithms and data structures has received considerable attention. However much less has been done to evaluate their performance, in particular, with parallel disks or when running on large inputs with sizes that really require external memory.

We present a software library Stxxl, that enables practice-oriented experimentation with huge data sets. Stxxl is an implementation of the C++ standard template library STL for external memory computations. It supports parallel disks, overlapping between I/O and computation and is the first external memory algorithm library that supports the pipelining technique that can save more than half of the I/Os.
Stxxl has already been used for the following applications: implementations of external memory algorithms for computing minimum spanning trees, connected components, breadth-first search decompositions, constructing suffix arrays, and computing social network analysis metrics for huge graphs.

We present a new speedup technique for route planning that exploits the hierarchy inherent in real world road networks. Our algorithm preprocesses the eight digit number of nodes needed for maps of the USA or Western Europe in a few hours using linear space. Shortest (i.e. fastest) path queries then take around eight milliseconds to produce exact shortest paths. This is about 2000 times faster than using Dijkstra's Algorithm.

The algorithms from Computational Geometry have applications in many areas like Robotics, Geographic Information Systems, Networks and Communications, Facility Location. Computational Biology is another area where the techniques developed in Computational Geometry can be applied. Examples of the problems in biochemistry are protein docking, protein motion, collision detection, rigidity analysis of molecular graphs. We will discuss these problems and geometric approaches to solve them.

We study a memory allocation problem for parallel processors. We wish to share memory between processors in order to avoid wasting it. To minimize contention, we allow a single memory to be accessed by only two processors at a time. We give a bin packing formulation for this problem and present an algorithm which has approximation ratio 1.4.

In drahtlosen Sensornetzen kann es sinnvoll sein Daten zwischen zwei Knoten auf mehrerern, disjunkten Wegen zu verschicken. Dabei ist es unter Umständen möglich, den sogenannten "Wireless Multicast Advantage" auszunutzen. Dieser entsteht dadurch, dass aufgrund der Natur des Funkmediums Nachrichten, die von einem Knoten gesendet werden, von mehreren Knoten gleichzeitig aufgefangen werden können. Durch diesen Vorteil wird das Problem eine energieoptimale Menge von disjunkten Wegen zu finden jedoch NP-schwer. Der Vortrag stellt einige Ergebnisse zur Approximation des Problems vor.

We are given the following problem: let a set P of n points in a polygonal domain be given, as well as a parameter k. Our task is to place k additional points, such that the resulting set is "nicely distributed", i.e., new points should preferably be placed in sparse regions. This problem has applications in GIS and computer graphics. We give a possible formal statement of the problem, argue that is hard to solve, and take a stab at an approximation algorithm.

Eine interessante Fragestellung zur Erforschung von geometrischen Spannern ist folgende: Gegeben eine endliche Punktemenge in der Ebene, was ist der minimale Streckfaktor, den ein planarer Graph haben kann, der alle Punkte entweder als Knoten oder auf Kanten enthält? Dabei ist jede Kantenform erlaubt, solange eine differenzierbare Kurve zugrundeliegt.

Ebbers-Baumann, Grüne und Klein haben gezeigt, dass jede Punktemenge in einem "Blümchenmuster"-Graph eingebettet werden kann, dessen Streckfaktor höchstens 1.678 ist. Als untere Grenze galt lange pi/2, die bestmögliche Schranke für eine Punktemenge, die auf einem Kreis eingebettet werden muss. (Streckfaktor eines Kreises: halber Kreisumfang geteilt durch Durchmesser = pi/2.) Allerdings wurde auch schon lange vermutet, dass es Punktemengen gibt, deren optimale Einbettung mehrere inzidente geschlossene Kurven enthalten muss, und dass deshalb die untere Schranke größer als pi/2 ist, da diese Kurven dann keine Kreise mehr sein können. Der Vortrag beweist dieses Ergebnis von Dumitrescu, Ebbers-Baumann, Grüne, Klein und Rote, die unter Ausnutzung eines disk-packing Resultats eine untere Schranke von pi/2 * 10^-11 zeigen konnten.

Clustering eine Grundtechnik im Umgang mit unübersichtlichen Datenmengen. Speziell im Kontext von großen Datenmengen ist es wichtig, dass die verwendeten Clustering-Algorithmen bestimmte Konsistenz-Eigenschaften erfüllen: je mehr Datenpunkte zur Verfügung stehen, desto verläßlicher und stabiler soll die vom Algorithmus konstruierte Partition der Daten sein. Um diese Eigenschaft zu untersuchen, nimmt man an, daß die Datenpunkte zufällig gemaß einer unbekannten Verteilung aus einem Datenraum gezogen werden. Die Frage der Konsistenz besteht dann darin, die Konvergenz der konstruierten Partitionen für wachsende Stichprobengröße zu zeigen.

Wir wollen die Frage der Konsistenz für die Klasse der Spektral-Clustering Algorithmen untersuchen. Spektral-Clustering benutzt Eigenvektoren der Graph-Laplace-Matrix des Ähnlichkeitsgraphs der Datenpunkte, um eine Partition der Daten zu konstruieren. Wir können zeigen, daß verschiedene Varianten von Spektral-Clustering ("normalisiert" oder "unnormalisiert") sehr verschiedene Konsistenzeigenschaften besitzen. Während die normalisierte Variante immer konvergiert, gilt Konvergenz für die unnormalisierte Variante nur unter sehr starken Zusatzbedingungen. In theoretischen und praktischen Beispielen kann man zeigen, daß diese Bedingungen in Anwendungen oft verletzt sind. Deshalb empfehlen wir, immer die normalisierte Variante des Algorithmus zu verwenden.

Traditional problems in graph visualization involve the layout of a single graph, while problems in simultaneous graph visualization involve the layout of multiple related graphs. A series of related graphs may arise from one relation between a set of objects as it evolves through time or from several relationships defined on the same set of objects. In simultaneous embedding, nodes are placed in the exact same locations in all the graphs and a series of graphs is simultaneously embeddable if it is possible to find node locations that yield straight-line crossing-free drawings for each of the individual graphs.

We present polynomial-time algorithms for simultaneous embedding of various classes of planar graphs and prove that some classes of graphs cannot be simultaneously embedded. Further, we present a near-linear time algorithm for visualizing graphs that evolve through time and demonstrate its application to problems in software engineering and databases.

Given a set P of points in the plane, a corridor is the region that lies between two parallel lines. We are interested in the following two corridor problems. (a) Given an integer k < n, find the narrowest corridor that contains at least k of the points in P. (b) Given a real w, find the corridor of width w that contains as many points of P as possible. It turns out that for solving these problems duality helps.

Im Bereich Motion Planning geht es oft darum, einen punktförmigen Roboter von einem Start- zu einem Zielpunkt zu bringen, ohne durch polygonale Hindernisse zu fahren. In einem zum Titel dieses Vortrags gleichnamigen Paper beschreiben die Autoren, Ron Wein, Jur van den Berg und Dan Halperin, wie man solche Wege so berechnen kann, dass sie "natürlich" aussehen, d. h. weder den Wänden zu nahe kommen noch allzu große Umwege darstellen.

Es wird Aroras Methode zum Finden eines PTAS für das Traveling Salesman Problem vorgestellt und diskutiert, auf welche geometrischen Probleme sein Ansatz verallgemeinert werden kann.

Übersicht				Next talk

				Winter term 2008
				Summer term 2008
				Winter term 2007
				Summer term 2007
				Winter term 2006
				Summer term 2006
				Winter term 2005
				Summer term 2005

Winter term 2008
Optimisation of Clustering Algorithms for the Identification of Customer Profiles from Shopping Cart Data
	Date	Fri, 19 Dec 2008, 14:00
	Location	room SR 301
	Speaker	Stefanie Nagel, Diplomarbeiterin

Finding Important Edges for Routing in Networks
	Date	Tue, 16 Dec 2008, 14:00
	Location	room SR 301
	Speaker	Martin Wolff
	Abstract	A fast method for computing highway node hierarchies is developed. The result is very fast preprocessing at the cost of somewhat larger query times.

Graph-Planarisieren durch Verschieben von Knoten
	Date	Tue, 9 Dec 2008, 14:00
	Location	room SR 301
	Speaker	Michael Ziller, Studienarbeiter

Scheduling and Topology Control in Wireless Sensor Networks
	Date	Tue, 11 Nov 2008, 14:00
	Location	room SR 301
	Speaker	Markus Völker, Diplomarbeiter
	Abstract	Within recent years, wireless sensor networks became a very popular tool for distributed monitoring of various physical and environmental conditions. Thanks to the ongoing miniaturization of the required hardware, this trend is likely to continue. In this thesis, we study the problems of scheduling and topology control in wireless networks. We consider both, networks with fixed transmission powers, and networks with freely adjustable transmission powers. For the scheduling problem, several methods for the computation of optimum schedules, as well as the computation of upper and lower bounds on the length of optimum schedules, are presented and analyzed. Additionally, various optimization possibilities are described. All methods have been implemented and are used in an experimental section to gain additional insights into the properties of wireless networks. Subsequently, the scheduling heuristics are extended to topology control algorithms. Goal of the topology control algorithms is the computation of topologies whose links are efficient to schedule. At the same time, the resulting topologies are required to conserve certain properties of the original network such as connectivity. The proposed topology control algorithms are compared to various existing algorithms using several quality measures for network topologies. A central part of this thesis is dedicated to the evaluation of constraint programming as a tool to solve scheduling problems under the physically motivated SINR model for wireless networks. For this purpose, constraint programming is compared to integer linear programming and several experiments are performed to highlight the pros and cons of both approaches. All constraint programs have been solved using the freely available Gecode solver which is described to some detail in the beginning of this thesis.

Out-of-the-Box Phrase Indexing
	Date	Wed, 29 Oct 2008, 13:00
	Location	room SR 301
	Speaker	Frederik Transier, ITI Sanders
	Abstract	Phrase searches are an important operation on text search engines. This talk shows how inverted index based text search engines can be improved to achieve reduced reponse times for phrase queries.

Stabilisatorgruppen in Aut(Fz)
	Date	Tue, 14 Oct 2008, 14:00
	Location	room SR -102
	Speaker	Myriam Freidinger, Diplomarbeiterin
	Abstract	Die betrachteten Stabilisatorgruppen sind Untergruppen von Aut(Fz) von endlichem Index, zu denen bisher nur sehr wenig bekannt ist. Sie können beispielsweise verwendet werden, um die Veechgruppe einer Überlagerung einer primitiven Translationsfläche zu bestimmen. Ziel des Vortrags ist die Vorstellung eines effizienten Algorithmus zur Berechnung des Stabilisators einer Untergruppe der freien Gruppe, sowie die Betrachtung heuristischer Maßnahmen zur Laufzeitverbesserung.

Summer term 2008
Design and Experimental Evaluation of A Local Graph Clustering Algorithm
	Date	Fri, 8 Aug 2008, 14:00
	Location	room SR 301
	Speaker	Christian Schulz, Studienarbeiter

Parameterized Complexity Analysis and Algorithm Design: A Natural Mission in Social Choice, Meta-Search, and Multi-Agent Systems
	Date	Fri, 18 Jul 2008, 14:00
	Location	room 231, Kollegiengebäude am Ehrenhof
	Speaker	Mike Fellows, University of Newcastle, Australien

Effizientes Starten und Verteilen von Threads
	Date	Fri, 11 Jul 2008, 14:00
	Location	room SR 301
	Speaker	Jakob Blomer, Diplomarbeiter ITI Sanders

Effiziente Tourenplanung für Pickup- und Delivery-Verkehre
	Date	Fri, 13 Jun 2008, 15:00
	Location	room PTV, Stumpfstraße 1
	Speaker	Johannes Spallek, Diplomarbeiter ITI Sanders/PTV

Set Cover Functions für boolsche Terme oder: wieder kein Beweis für P = NP
	Date	Fri, 13 Jun 2008, 14:00
	Location	room SR 301
	Speaker	Bastian Katz

Rainbow Sort: Sorting at the Speed of Light
	Date	Tue, 27 May 2008, 15:00
	Location	room SR 131
	Speaker	Dominik Schultes, ITI Sanders
	Abstract	Rainbow Sort is an unconventional method for sorting, which is based on the physical concepts of refraction and dispersion. It is inspired by the observation that light that traverses a prism is sorted by wavelength. At first sight this "rainbow effect" that appears in nature has nothing to do with a computation in the classical sense, still it can be used to design a sorting method that has the potential of running in O(n) with a space complexity of O(n), where n denotes the number of elements that are sorted.

Neighborhood Graphs in Clustering
	Date	Mon, 26 May 2008, 14:00
	Location	room SR 236
	Speaker	Markus Maier, MPI für biologische Kybernetik

Reach for A*: Fast Driving Directions on Road Networks
	Date	Mon, 26 May 2008, 11:30
	Location	room SR 131
	Speaker	Renato Werneck, Microsoft Research, USA
	Abstract	This talk will describe fast algorithms for computing exact point-to-point shortest paths (driving directions) on road networks. Our approach is a combination of two techniques: reach-based pruning eliminates local intersections, while landmark-based A* search directs the search towards the goal. On the road networks of the USA and Western Europe, an average query visits no more than a thousand road intersections (out of roughly 20 million), which is four orders of magnitude better than Dijkstra's algorithm. Besides presenting an overview of the basic techniques, the talk will discuss a few recent developments, such as an improved algorithm for computing landmarks. Joint work with Andrew Goldberg and Haim Kaplan.

Load-Balancing in Web Search Engines
	Date	Fri, 16 May 2008, 14:00
	Location	room SR 301
	Speaker	Paul Dütting, Diplomarbeiter
	Abstract	Large-scale web search engines typically split the overall index into hundreds of subindices. Thus, not only different queries can be run in parallel on different servers but also the work required to answer a single query can be split across multiple servers. For high resource utilization and throughput the overall workload has to be balanced over the available servers. Experiments with query logs from AltaVista and AllTheWeb and 20M web pages from Stanford's WebBase suggest that (a) the overall load is roughly balanced over the subindices and that (b) the load generated by individual queries is rather tiny. Based on these insights we present a refined theoretical framework and devise several highly competitive loadbalancing strategies.

Contraction Hierarchies
	Date	Tue, 15 Apr 2008, 15:45
	Location	room SR 301
	Speaker	Robert Geisberger, Diplomarbeiter, ITI Sanders
	Abstract	We present a route planning technique solely based on the concept of node contraction. The nodes are first ordered by 'importance'. A hierarchy is then generated by iteratively contracting the least important node. Contracting a node v means replacing shortest paths going through v by shortcuts. We obtain a hierarchical query algorithm using bidirectional shortest-path search. The forward search uses only edges leading to more important nodes and the backward search uses only edges coming from more important nodes. For fastest routes in road networks, the graph remains very sparse throughout the contraction process using rather simple heuristics for ordering the nodes. We have five times lower query times than the best previous hierarchical Dijkstra-based speedup techniques and a negative space overhead, i.e., the data structure for distance computation needs less space than the input graph. CHs can be combined with many other route planning techniques, leading to improved performance for many-to-many routing, transit-node routing, goal-directed routing or mobile and dynamic scenarios.

Winter term 2007
LP-basierte Heuristiken für Graphenclusterung mit Modularity als Qualitätsmaß
	Date	Fri, 28 Mar 2008, 14:00
	Location	room SR 301
	Speaker	Manuel Krings, Studienarbeiter

Zeitexpandiertes Graphenclustern — Modellierung und Experimente
	Date	Thu, 20 Mar 2008, 14:00
	Location	room SR 301
	Speaker	Dieter Glaser, Diplomarbeiter

On Unfolding Lattice Chains, Trees and Polygons
	Date	Fri, 14 Mar 2008, 11:15
	Location	room SR 301
	Speaker	Sheung-Hung Poon, National Tsing Hua University, Taiwan

Systematic Combination of Speed-Up Techniques for Exact Shortest-Path Queries
	Date	Tue, 19 Feb 2008, 14:00
	Location	room SR 301
	Speaker	Dennis Schieferdecker, Diplomarbeiter

Goal-Directed Speed-Up Techniques for Shortest-Path Queries in Timetable Networks
	Date	Fri, 8 Feb 2008, 14:00
	Location	room SR 301
	Speaker	Thomas Pajor, Studienarbeiter

Determination of Maximally Stable Extremal Regions in Large Images
	Date	Fri, 1 Feb 2008, 14:00
	Location	room SR 301
	Speaker	Jan Wassenberg, ITI Sanders

A Node's Perspective of Changing Properties in Dynamic Networks
	Date	Tue, 29 Jan 2008, 14:00
	Location	room SR 301
	Speaker	Lin Huang, Diplomarbeiterin

(Lokales) Scheduling von Übertragungen in Sensornetzen im SINR-Modell
	Date	Wed, 16 Jan 2008, 14:00
	Location	room 301
	Speaker	Markus Völker, Studienarbeiter

Berechnung des Stabilisators einer Untergruppe der freien Gruppe
	Date	Tue, 15 Jan 2008, 14:00
	Location	room SR 301
	Speaker	Myriam Freidinger, Diplomarbeiterin

Parallel Highway-Node Routing
	Date	Fri, 11 Jan 2008, 14:30
	Location	room SR 301
	Speaker	Manuel Holtgrewe, Studienarbeiter at ITI Sanders
	Abstract	Highway-Node Routing is a scheme for solving the shortest path problem showing excellent speedups. There also is a dynamic variant that allows changes to the cost function. Based on an existing, sequential implementation of this precomputation, we present a parallel version. We also present experimental results with the road network of Europe as the input. During the parallelization, problems with imbalanced load and memory bandwidth limitations were encountered. We evaluated several load balancing variants and also a modification that makes the problem more regular. We also considered a scheme that tries to exploit the shared cache structure of the used machine to lessen the memory bandwidth limitation. When making the problem more regular, the best variant achieves a speedup of 7.0 with 8 threads with no significant effect on query time. When the result is to be identical to the sequential version's, the best variant achieves a speedup of 5.9 with 8 threads.

Better Approximation of Betweenness Centrality
	Date	Fri, 11 Jan 2008, 14:00
	Location	room SR 301
	Speaker	Robert Geisberger, Studienarbeiter at ITI Sanders
	Abstract	Estimating the importance or centrality of the nodes in large networks has recently attracted increased interest. Betweenness is one of the most important centrality indices, which basically counts the number of shortest paths going through a node. Betweenness has been used in diverse applications, e.g., social network analysis or route planning. Since exact computation is prohibitive for large networks, approximation algorithms are important. In this paper, we propose a framework for unbiased approximation of betweenness that generalizes a previous approach by Brandes. Our best new schemes yield significantly better approximation than before for many real world inputs. In particular, we also get good approximations for the betweenness of unimportant nodes.

Exakte Kreuzungsminimierung in Kreislayouts
	Date	Tue, 8 Jan 2008, 14:00
	Location	room SR 301
	Speaker	Moritz Kobitzsch, Studienarbeiter

Summer term 2007
Approximative Matchings in Cross-Match-Tests
	Date	Wed, 5 Sep 2007, 14:00
	Location	room SR 301
	Speaker	Tanja Hartmann, Studienarbeiterin
	Abstract	Der Cross-Match-Test ist ein nichtparametrischer Zweistichprobentest, der sich eines minimalen, perfekten Matchings bedient um eine geeignete Teststatistik zu definieren. Ziel der Studienarbeit war es zu untersuchen, ob neben dem exakten Matchingalgorithmus von Edmonds auch nicht exakte, dafür aber schnellere und einfacher zu implementierende Algorithmen für die Anwendung innerhalb des Cross-Match-Tests geeignet sind. Die experimentelle Untersuchung beschränkte sich dabei auf den Algorithmus nach Wattenhofer und Wattenhofer als Beispiel approximativer Matchingalgorithmen.

Data Harvesting in Sensor Networks
	Date	Fri, 31 Aug 2007, 14:00
	Location	room SR 301
	Speaker	Bastian Katz

Graphersetzung für eine Zwischendarstellung im Übersetzerbau
	Date	Wed, 8 Aug 2007, 14:00
	Location	room SR 236
	Speaker	Veit Batz, IPD Goos

Verhalten und Qualität von k-Betweenness-Clusterungen
	Date	Tue, 31 Jul 2007, 14:00
	Location	room SR 131
	Speaker	Abian Blome, Studienarbeiter
	Abstract	In diesem Vortrag wird der k-Betweenness-Algorithmus, eine Variante des Newman-Girvan-Algorithmus, präsentiert. Im Anschluss soll das Verhalten von diesem sowie die empirischen Ergebnisse zu Laufzeitverbesserung und Qualitätseinbußen bei verschiedener Parameterauswahl vorgestellt werden.

Dynamische Kürzeste-Wege-Bäume
	Date	Fri, 27 Jul 2007, 14:00
	Location	room SR 301
	Speaker	Reinhard Bauer

Load-Balancing in Web Search Engines
	Date	Tue, 17 Jul 2007, 13:00
	Location	room SR 301
	Speaker	Paul Dütting, Diplomarbeiter
	Abstract	Web search engines answer hundreds of millions of queries per day. Answering one user query requires a short amount of processing on thousands of machines. For fast query processing it is important to efficiently balance the load over the involved machines. Interestingly, this load has several properties that are not captured by existing load-balancing models. We present and analyze a refined model that takes these characteristics into account.

An Optimal Bound for the MST Algorithm to Compute Energy-Efficient Broadcast Trees in Wireless Networks
	Date	Mon, 9 Jul 2007, 12:30
	Location	room SR 131
	Speaker	Simon Friedberger, Seminarstudent

Landmark Selection and Greedy Landmark-Descent Routing for Sensor Networks
	Date	Mon, 9 Jul 2007, 11:30
	Location	room SR 131
	Speaker	Felix Brandt, Seminarstudent

MLS: An Efficient Location Service for Mobile Ad-Hoc Networks
	Date	Thu, 5 Jul 2007, 15:00
	Location	room SR 301
	Speaker	Roland Stühmer, Seminarstudent

Routing, Anycast, and Multicast for Mesh and Sensor Networks
	Date	Thu, 5 Jul 2007, 14:00
	Location	room SR 301
	Speaker	Florian Merz, Seminarstudent

Schnelle Berechnung von großen Matchings
	Date	Tue, 29 May 2007, 14:00
	Location	room SR 131
	Speaker	Ignaz Rutter
	Abstract	Es gibt eine Reihe von unteren Schranken für die Kardinalität von größten Matchings in gewissen Graphenklassen. Beispielsweise besitzt jeder 3-reguläre Graph ein Matching der Größe (4n-1)/9. Die Arbeit beschäftigt sich mit der Fragestellung, ob Matchings dieser Mindestgröße (von denen man ja weiß, dass sie existieren) schneller gefunden werden können als durch Berechnung eines größten Matchings.

Protein Domain Decomposition Using Spectral Graph Partitioning
	Date	Tue, 17 Apr 2007, 13:30
	Location	room SR 131
	Speaker	Steffen Lang, Studienarbeiter at ITI Wagner

Robuste Zentralitätsmaße in einfachen ungerichteten Graphen
	Date	Tue, 3 Apr 2007, 14:00
	Location	room SR 236
	Speaker	Jakob Blomer, Studienarbeiter at ITI Wagner

Winter term 2006
Geradlinige Gitterzeichnungen planarer Graphen
	Date	Thu, 15 Mar 2007, 14:00
	Location	room SR 301
	Speaker	Marcus Krug, Diplomarbeiter at ITI Wagner
	Abstract	Planare Graphen werden häufig geradlinig auf einem ganzzahligen Gitter gezeichnet. Durch die Geradlinigkeit der Kanten lassen sich die Graphen vom Betrachter leicht erfassen. Darüber hinaus vermeidet man durch ganzzahlige Arithmetik, dass die Planarität der Zeichnung beim Runden der Koordinaten zerstört wird. Generell ist man unter anderem an Zeichnungen mit geringem Flächenbedarf interessiert. Ziel des Vortrags ist es zu zeigen, dass es NP-schwer ist zu entscheiden, ob ein planarer Graph auf einem Gitter mit vorgegebenem Flächenbedarf gezeichnet werden kann.

Minimale Schnitte und Schnittbäume
	Date	Tue, 20 Feb 2007, 14:00
	Location	room SR 236
	Speaker	Myriam Freidinger, Studienarbeiterin at ITI Wagner
	Abstract	Ziel dieser Arbeit ist es zu untersuchen, inwieweit sich der Algorithmus von Stoer und Wagner dazu verwenden lässt, einen minimalen Schnittbaum zu erzeugen. Der Algorithmus von Stoer und Wagner berechnet den minimalen Schnitt in einem Graphen und erzeugt im Laufe dessen insgesamt n − 1 unterschiedliche Schnitte des Graphen. Eine genauere Untersuchung dieser Schnitte ergab leider, dass sie sich nicht dazu eignen, einen minimalen Schnittbaum zu erstellen. Sie sind zwar linear unabhängig und erfüllen die notwendigen Eigenschaften, dass sie sich paarweise nicht kreuzen, das Gewicht des aus ihnen berechneten Schnittbaumes ist aber nicht minimal. Auch als Heuristik erzielt der Algorithmus keine guten Resultate. Als zweiten Teil der Arbeit wurden Heuristiken zu Schnittbäumen untersucht. Die Heuristiken des maximalen kurzen Baumes und des daraus resultierenden optimierten Baumes laufen schnell und zuverlässig auf den getesteten Graphen. Eine Gütegarantie mit Faktor 2 sichert konstant gute Ergebnisse.

Approximationsalgorithmen für gewichtete Matchings in Cross-Match-Tests
	Date	Tue, 30 Jan 2007, 14:00
	Location	room SR 236
	Speaker	Tanja Hartmann, Studienarbeiterin at ITI Wagner
	Abstract	Bei Cross-Match-Tests handelt es sich um nichtparametrische, multivariate Zwei-Stichproben-Verteilungstests, deren Teststatistik auf minimal gewichteten Matchings basiert. Desto ähnlicher die Verteilungen der zugrundeliegenden Stichproben, desto mehr Cross-Matches zwischen den beiden Stichproben erwartet man. Angesichts der Laufzeit des exakten Matchingalgorithmus von Edmonds (1965) soll nun untersucht werden, in wie weit die Verwendung schnellerer Approximationsalgorithmen das Verhalten der Teststatistik verändert.

Efficient Data Structures Libraries
	Date	Tue, 16 Jan 2007, 14:00
	Location	room SR 236
	Speaker	Leonor Frias, Universitat Politecnica de Catalunya
	Abstract	Modern software design relies on the interaction and extension of well-defined, robust and flexible predefines software components. Data structures libraries define interfaces and implement fundamental data structures and algorithms. Nowadays, they are included as part of most programming languages and so, they are very accessible. As an specific case, we focus on the C++ Standard Library, and more in particular, on the Standard Template Library(STL). On the other hand, in the last years there have been great advances in the algorithmic communit and hardware: managing large volumes of data, taking advantage of the cache hierarchy, multicore computers... But data structures libraries do not take much advantage of this work. Indeed, the requirements or assumptions are oftenly quite different. But anyway, they are using the same abstractions. The goal of my thesis is enhancing some STL components with up-to-date knowledge on algorithms and data structures while keeping with STL requirements. In this talk, I will present briefly specific problems I have been dealing with.

Clustern mit beschränkter Clustergröße
	Date	Tue, 19 Dec 2006, 14:00
	Location	room SR 236
	Speaker	Jochen Speck, Studienarbeiter at ITI Wagner

Survey on Internet Topology Generators on the AS Level
	Date	Fri, 15 Dec 2006, 13:30
	Location	room SR 301
	Speaker	Lin Huang, Studienarbeiterin at ITI Wagner
	Abstract	As the Internet develops, the simulation of the Internet becomes an urgent request nowadays. To obtain an accurate simulation, we need to model the Internet topology. The modeling of the Internet topology started a from random model to the hierarchical model and then it developed to a scale-free network model. Many characteristics of topology have been analyzed with the corresponding metrics, including the prominent Power-Law distribution (eg. frequency, degree). Modeling the Internet topology is still an important open problem, since an accurate topological model can have significant impact on network research. In this paper we discuss some popular Internet topology models and several relevant Internet topology generators at the autonomous system (AS) level, one of which has been developed at our institute.

Minimum-Energy Reliable Paths
	Date	Fri, 3 Nov 2006, 14:00
	Location	room SR 301
	Speaker	Steffen Mecke
	Abstract	Viele Routing-Algorithmen die energieminimale Wege suchen, berücksichtigen nicht, dass Verbindungen unzuverlässig sein können und so zusätzliche Energie aufgewendet wird, wenn die Übertragung wiederholt werden muss. In einem Artikel von Dong, Banerjee, Adler und Misra wurde nun ein Modell entworfen, das dies zu berücksichtigen versucht und Algorithmen besprochen, die in diesem Modell energieminimale Wege finden.

Allgemeine Testumgebung für das Evaluieren von Algorithmen in Java
	Date	Tue, 31 Oct 2006, 14:00
	Location	room SR 301
	Speaker	Marco Gaertler

Efficient Computation of Many-to-Many Shortest Paths
	Date	Fri, 13 Oct 2006, 14:00
	Location	room SR 301
	Speaker	Sebastian Knopp, Diplomarbeiter at ITI Wagner

Summer term 2006
Reach for A*: an Efficient Point-to-Point Shortest-Path Algorithm
	Date	Fri, 15 Sep 2006, 14:00
	Location	room SR -101
	Speaker	Andrew Goldberg, Microsoft Research, Silicon Valley
	Abstract	We study the point-to-point shortest path problem in a setting where preprocessing is allowed. We improve the reach-based approach of Gutman in several ways. In particular, we add shortcut arcs which reduce vertex reaches. Our modifications greatly reduce both preprocessing and query times. Our algorithm combines in a natural way with A* search, which yields significantly better query times and allows a wide range of time-space trade-offs. The resulting algorithms are quite practical for our motivating application, computing driving directions, both for server and for portable device applications.

Algorithms for Metro Map Layouts
	Date	Fri, 8 Sep 2006, 14:00
	Location	room SR 301
	Speaker	Damian Merrick, University of Sydney

Connectivity, Realization, and Enumeration of Cover Contact Graphs
	Date	Tue, 5 Sep 2006, 14:00
	Location	room SR 301
	Speaker	Pedro Reyes, Dept. Matematica Aplicada I, Universidad Sevilla
	Abstract	A Cover Contact Graph (CCG) is a graph defined by a pair G=(S,C), where S is a set of objects (called seeds) in the plane, and C is a collection of discs or triangles (called covers) covering the seeds, with the property that the interior of those discs or triangles are mutually disjoint. The contact graph of C is a CCG. We study three basic properties of CCG's taking into account the nature of the seeds and of the covers. Namely, whether there exists a connected CCG on a fixed seed set, whether is it possible to realize a given graph as a CCG, and finally we try to enumerate certain classes of CCG's. Different results about these three basic problems were presented at the 22nd European Workshop on Computational Geometry [1]. Here we will focus on some representative results concerning connectivity, realization or enumeration problems.
	Information	[1] M. Abellanas et al. Cover Contact Graphs. 22nd European Workshop on Computational Geometry, Delphi (2006), pp. 79-82.

Dynamic Speed-up Techniques for Dijkstra's Algorithm
	Date	Tue, 15 Aug 2006, 14:00
	Location	room SR 301
	Speaker	Reinhard Bauer, Diplomarbeiter at ITI Wagner
	Abstract	In diesem Abschlussvortrag zur Diplomarbeit werden dynamische Varianten bekannter Beschleunigungstechniken für den Dijkstra-Algorithmus vorgestellt werden, besonders der Multilevel- und der Reach-Technik.

Automatische Generalisierung - aktuelle Entwicklungen, ein neues Aggregationsverfahren und offene Probleme
	Date	Mon, 14 Aug 2006, 14:00
	Location	room SR 301
	Speaker	Jan Haunert, IKG, Universität Hannover
	Abstract	In der Kartographie versteht man unter dem Begriff Generalisierung die Aufgabe, einen kleineren Maßstab aus einer bestehenden Repräsentation abzuleiten. Hierbei sind verschiedene Teilprobleme wie Vereinfachung, Aggregation, Selektion und Typifizierung zu lösen. Einige dieser Probleme konnten in der Vergangenheit für bestimmte Objektklassen erfolgreich automatisiert werden. Generell ist allerdings weitere Forschung notwendig. Neben der Diskussion anderer Probleme wird insbesondere ein neues Verfahren zur Aggregation von Flächen präsentiert, welches für die Generalisierung von Landnutzungskarten entwickelt wurde. Der Information über Landnutzung wird eine große Bedeutung beigemessen, da sie eine wichtige Grundlage für topographische Karten darstellt. Abschließend werden einige neue Herausforderungen besprochen, die sich aus aktuellen Entwicklungen in der Geoinformatik ergeben. Hierbei ist insbesondere das Problem der inkrementellen Generalisierung zu nennen, zu dem Lösungsansätze aufgezeigt werden.

NP-Schwere von sektorgestützter Sensorlokalistion
	Date	Wed, 9 Aug 2006, 14:00
	Location	room SR -120
	Speaker	Bastian Katz

DGraphML - Ein XML-basiertes Dateiformat für dynamische Graphen
	Date	Wed, 2 Aug 2006, 15:00
	Location	room SR 301
	Speaker	Helge Ruben, Studienarbeiter WSI, Universität Tübingen

Visualisierung sehr großer Graphen
	Date	Wed, 2 Aug 2006, 14:00
	Location	room SR 301
	Speaker	Timo Bingmann, Studienarbeiter ITI Sanders
	Abstract	In dieser Studienarbeit wird untersucht, mit welchen Methoden sehr große Graphen wie ein Straßennetzwerk von Europa effizient und komfortabel visualisiert werden können. Als Ausarbeitung entsteht ein C++ Rahmenwerk für die Datenhaltung eines Graphen mit Attributen und ein Java Applet, das mit dem Datenhaltungs-Server mittels CORBA kommuniziert. Das Rahmenwerk kann leicht in bestehende Graphanwendungen integriert werden, um deren Algorithmen zu animieren. Um die Geschwindigkeit einer Ausschnittsanfrage zu erhöhen, wird die mehrdimensionale Indexstruktur R-Tree verwendet. Diese ermöglicht Anfragezeiten, die linear zur Anzahl der zurückgelieferten Kanten und unabhängig vom gewählten Ausschnitt sind. Es können komplexe Filterausdrücke aus Vergleichsbedingungen mit boolschen und arithmetische Operatoren verwendet werden, um die angezeigten Kanten in einem Visualisierungsauschnitt einzuschränken und so komfortabel bestimmte Aspekte der Anwendungs-Algorithmen zu untersuchen oder hervorzuheben.

Die ungarische Methode und eine geometrische Anwendung
	Date	Fri, 28 Jul 2006, 14:00
	Location	room SR 301
	Speaker	Ignaz Rutter, Diplomarbeiter bei GeoNet

Reporting flock patterns
	Date	Wed, 26 Jul 2006, 14:00
	Location	room SR -120
	Speaker	Florian Hübner, ITI Wagner
	Abstract	Data representing moving objects is rapidly getting more available, especially in the area of wildlife GPS tracking. It is a central belief that information is hidden in large data sets in the form of interesting patterns. One of the most common spatio-temporal patterns sought after is flocks. A flock is a large enough subset of objects moving along paths close to each other for a certain pre-defined time. We give a new definition that we argue is more realistic than the previous ones, and we present fast approximation algorithms to report flocks. The algorithms are analysed both theoretically and experimentally.

Exploiting Multi-Core Parallelism in Modern Architectures
	Date	Fri, 14 Jul 2006, 14:00
	Location	room SR 301
	Speaker	Johannes Singler, ITI Sanders

In-Memory Text Index: Abmischen von Listen
	Date	Wed, 12 Jul 2006, 14:00
	Location	room SR -120
	Speaker	Frederik Transier, ITI Sanders

Linearzeitalgorithmus zur Vierfärbung planarer Graphen?
	Date	Wed, 5 Jul 2006, 14:00
	Location	room SR -120
	Speaker	Steffen Mecke
	Abstract	1977 veröffentlichten K. Appel und W. Haken ihren berühmten Beweis zu der seit 100 Jahren offenen 4-Farben-Vermutung. Diese besagt, dass jeder planare Graph eine Knotenfärbung mit höchstens 4 Farben zulässt. Der Beweis von Appel und Haken war zunächst umstritten, vor allem deshalb, weil er Computer benutzt um gewisse Fallunterscheidungen durchzuführen. Zwanzig Jahre später veröffentlichten N. Robertson, D. Sanders und R. Thomas einen neuen, einfacheren Beweis, der aber immer noch die Hilfe von Computern erfordert. Die Autoren geben in dieser Arbeit auch einen Algorithmus an, der in quadratischer Zeit eine solche 4-Färbung berechnet. In meinem Vortrag werde ich zunächst einen kurzen Überblick zur Struktur des Beweises geben. Hauptsächlich geht es jedoch darum, über eine mögliche Verbesserung des eigentlichen Algorithmus zur Vierfärbung von quadratischer Zeit zu Linearzeit zu spekulieren.
	Information	Folien Literatur: M. Aigner: Graphentheorie -- Eine Entwicklung aus dem 4-Farben Problem, Teubner Stuttgart, 1984 (vergriffen, Unibib). N. Robertson, D. P. Sanders, P. D. Seymour und R. Thomas: "The four colour theorem", J. Combin. Theory Ser. B. 70 (1997), 2-44.

Verifikation von Heap-Algorithmen
	Date	Fri, 30 Jun 2006, 14:00
	Location	room SR 301
	Speaker	Thomas Käufl, ITI Sanders
	Abstract	Der Heapsort-Algorithmus gilt als eines der am schwierigsten zu verifizierenden Sortierverfahren. Der Vortrag stellt die grundlegenden Algorithmen zur Behandlung von Heaps dar. Im Unterschied zu den anderen Vorträgen dauert der Vortrag 40 Minuten. In der ersten Hälfte wird exemplarisch erlaeutert, wie Programme spezifiziert und verifiziert werden.

Force-Directed Approaches to Sensor Localization
	Date	Wed, 28 Jun 2006, 10:00
	Location	room SR 131
	Speaker	Stephen Kobourov, University of Arizona

Kürzeste-Wege-Suche durch hierarchische Dekomposition
	Date	Tue, 27 Jun 2006, 14:00
	Location	room SR 131
	Speaker	Kirill Müller, Diplomarbeiter ITI Wagner
	Abstract	In dieser Arbeit wird eine Erweiterung des Multi-Level-Ansatzes [1] zur exakten Bestimmung kürzester Wege vorgestellt. Der Eingabegraph wird in einer Vorberechnungsphase in eine Komponentenhierarchie zerlegt, aus der Hilfsdaten generiert werden. Die Hilfsdaten bestehen hier aus vielen kleinen Graphen, aus denen für jede Distanz-Anfrage leicht ein Suchraum-Graph kombiniert werden kann, in dem die Distanz zwischen zwei dedizierten Knoten der angefragten Distanz entspricht. Da der Suchraum-Graph sehr klein im Vergleich zum Eingabegraphen ist, geht die eigentliche Suche sehr schnell vonstatten. Die Dauer einer Suchanfrage kann garantiert werden, diese hängt vom Umfang der Hilfsdaten und von der Dauer der Vorberechnung ab. Die Vorberechnung selbst ist gut parallelisierbar. Die Hilfsdaten können im Externspeicher verwaltet werden, in diesem Fall werden pro Anfrage nur wenige Zugriffe auf den Externspeicher benötigt. Wenn die Hilfsdaten im Arbeitsspeicher abgelegt werden, ist die Anfragezeit für große Straßen-Netzwerke mit anderen aktuellen Ansätzen [2, 3] vergleichbar. [1] Martin Holzer, Frank Schulz, and Dorothea Wagner. Engineering multi-level overlay graphs for shortest-path queries. [2] Peter Sanders and Dominik Schultes. Highway hierarchies hasten exact shortest path queries. [3] Andrew Goldberg, Haim Kaplan, and Renato Werneck. Reach for A*: Efficient point-to-point shortest path algorithms.
	Information	[1] [pdf] [2] [pdf] [3] [pdf]

Schnittbasen
	Date	Fri, 23 Jun 2006, 14:00
	Location	room SR 301
	Speaker	Dorothea Wagner

Discovery, Composition and Mediation of services in a Global Service – Oriented Architecture
	Date	Wed, 21 Jun 2006, 14:00
	Location	room SR -120
	Speaker	Vela Spasova, Studienarbeiter am ITI Wagner
	Abstract	In this research work, we propose to address issues of discovery, composition and mediation of services and more specifically of Web services. The composition and discovery process is a challenging task because Web services are expected to be numerous, autonomous and heterogeneous. We model the problem as a forward shortest path problem in a hypergraph and we adopted solutions developed in the context of AI search for computation of forward shortest hyperpaths in hypergraphs, which is a NP-complete problem. The research proposes three algorithms based on Dijkstra’s, A* and forward chaining algorithm for automatic optimal or near –optimal composition of Web services. These algorithms are implemented in C. The empirical performance of the proposed algorithms and their variants are comparatively evaluated.

Paging with Request Sets
	Date	Wed, 14 Jun 2006, 14:00
	Location	room SR -120
	Speaker	Rob van Stee, ITI Sanders
	Abstract	A generalized paging problem is considered. Each request is expressed as a set of u pages. In order to satisfy the request, at least one of these pages must be in the cache. Therefore, on a page fault, the algorithm must load into the cache at least one page out of the u pages given in the request. The problem arises in systems in which requests can be serviced by various utilities (e.g., a request for a data that lies in various web-pages) and a single utility can service many requests (e.g., a web-page containing various data). The server has the freedom to select the utility that will service the next request and hopefully additional requests in the future. The case u=1 is simply the classical paging problem, which is known to be polynomially solvable. We show that for any u>1 the offline problem is NP-hard and hard to approximate if the cache size k is part of the input, but solvable in polynomial time for constant values of k. We consider mainly online algorithms, and design competitive algorithms for arbitrary values of k,u. We study in more detail the cases where u and k are small. We also give an algorithm which uses resource augmentation and which is asymptotically optimal for u=2.

A Drawing Convention for Micro/Macro Graphs
	Date	Fri, 9 Jun 2006, 14:00
	Location	room SR 301
	Speaker	Michael Baur
	Abstract	We propose a drawing convention for micro/macro graphs, i.e.relational structures at two levels of detail. Prototypical examples for macro-level structures are quotient graphs, which result from contracting sets of vertices in a given (micro-level) graph. While the coarse macro graph can be laid out in any style fit, its elements are rendered with sufficient thickness to draw the underlying micro graph on top of them, so that the contribution of micro-level elements to macro-level structure becomes apparent. Moreover, a concrete instantiation of micro-graph layout based on a circular layout technique is given.

Engineering Highway Hierarchies
	Date	Wed, 7 Jun 2006, 14:00
	Location	room SR 301
	Speaker	Dominik Schultes, ITI Sanders
	Abstract	At ESA 2005, we presented a shortest path algorithm that allows fast point-to-point queries in graphs using preprocessed data. Here, we give an extensive revision of our method. It allows faster query and preprocessing times, it reduces the size of the data obtained during the preprocessing and it deals with directed graphs. Preprocessing the network of Western Europe, which consists of about 18 million nodes, takes 21 minutes and yields 66 bytes of additional data per node. Then, random queries take 1.94 ms on average.

Correlation Clustering
	Date	Fri, 2 Jun 2006, 13:00
	Location	room SR 301
	Speaker	Jochen Speck, Studienarbeiter at GeoNet

Processing Huge Graphs with STXXL
	Date	Wed, 31 May 2006, 14:00
	Location	room SR 301
	Speaker	Roman Dementiev, ITI Sanders
	Abstract	STXXL is a library of basic I/O-efficient algorithms and data structures. It has interfaces of the standard C++ library STL, but can handle efficiently huge inputs that do not fit into internal memory of a computer. The library supports disk parallelism, pipelining of algorithms to save I/Os, overlapping between I/O and internal computation. We discuss algorithmic ideas of recent I/O-efficient graph algorithms for computing breadth first search level decompositions, minimum spanning forests and graph coloring, and present their STXXL implementations. We demonstrate that very large instances of these problems, taking up to hundreds of gigabytes just to represent the input, can be solved within few hours on a low-cost hardware.

Das Zirkulationsproblem - Algorithmen und Anwendungen
	Date	Fri, 26 May 2006, 13:15
	Location	room SR 301
	Speaker	Dimiter Ivanchev, New Bulgarian University und TU Sofia

Enumeration of Pseudo-Cliques
	Date	Wed, 24 May 2006, 15:45
	Location	room SR 301
	Speaker	Takeaki Uno, National Institute of Informatics, Japan
	Abstract	Clique enumeration is an important task in computer science. By the recent rapid growth of databases, automatic processing using cliques is getting more important. Thanks to the progress of computational power and database technologies, we can enumerate cliques of large graphs in time short enough in a practical sense. Now we are going to the next step. In practice, what we really want to find is clique-like structures, i.e. vertex sets having many edges in their induced subgraphs. Our motivation is that real world data may include some error, missing edges, and incompleteness. Cliques are a special case in which we can solve the problems easily. In this talk we address the problem of enumerating vertex sets having many edges in their induced subgraphs. We prove that straightforward approaches may not work, propose a polynomial time algorithm, and show results of computational experiments.

Optimal Broadcast for Fully Connected Networks
	Date	Tue, 16 May 2006, 14:00
	Location	room SR 131
	Speaker	Jesper Larsson Träff, C&C Research Laboratories, NEC Europe Ltd.
	Abstract	We present an optimal broadcast algorithm for fully connected networks under a linear communication cost model in which each processor can simultaneously send a message to one processor and receive a message from another. For any number of processors the number of communication rounds required to broadcast blocks of data is $N-1+\lceil \log p\rceil$ . For data of size , assuming that sending and receiving data units takes time $\alpha+\beta m$ , the best running time that can be achieved is $(\sqrt{(\lceil \log p\rceil -1)\alpha}+\sqrt{\beta m})^2$ . The algorithm has a regular communication pattern based on arc disjoint binomial trees, and has a binomial tree broadcast as a special case when the number of blocks to be broadcast is one. The same algorithm can therefore be used for all message sizes , and is furthermore well-suited for SMP clusters. We demonstrate significant practical improvements of up to a factor 1.5 over several other, commonly used broadcast algorithms.

Greedy Search Engine Loadbalancing
	Date	Tue, 2 May 2006, 13:15
	Location	room SR 301
	Speaker	Paul Dütting, Studienarbeiter am ITI Wagner
	Abstract	This student research project studies a variant of the load balancing problem with restricted assignments and permanent tasks which arises in web search engines. We show that for our variant of the problem the greedy scheduling algorithm achieves maximum machine load within a constant factor of the optimum. This result substantiates the popularity of the greedy algorithm amongst software engineers for balancing load among multiple machines and gives an interesting contrast to the result by Azar et al. showing that the competitive ratio of the greedy algorithm with restricted assignment and permanent tasks is Θ(log m), where m is the number of machines.

Winter term 2005
Benutzerorientierte Geovisualisierung
	Date	Fri, 24 Mar 2006, 11:00
	Location	room R 301
	Speaker	Martin Nöllenburg
	Abstract	Geovisualisierung ist ein aktuelles interdisziplinäres Forschungsgebiet, das sich mit der visuellen Exploration, Analyse, Synthese und Präsentation von räumlichen Daten beschäftigt. Neben den klassischen von Kartographen erzeugten Landkarten gibt es eine Fülle von interaktiven und dynamischen Methoden aus dem Bereich der Informationsvisualisierung, die auch zur Visualisierung von geographischen Daten benutzt werden können. Allerdings erfordern geographische Daten oft besondere Darstellungsformen. In diesem Vortrag werden mehrere Visualisierungstechniken vorgestellt, allerdings mit einem besonderen Fokus auf die Bedürfnisse menschlicher Benutzer und die Benutzbarkeit von Geovisualisierungssystemen.

A New Approximation Algorithm for Labeling Weighted Points with Sliding Labels
	Date	Tue, 21 Mar 2006, 14:00
	Location	room SR 301
	Speaker	Moritz Minzlaff, Studienarbeiter at GeoNet
	Abstract	I will present a polynomial-time approximation algorithm for labeling weighted points with horizontally sliding labels of unit height and given lengths. The aim is to maximize the total weight of the labeled points. The approach is based on a discretization, and two results are established: In general, the algorithm has an approximation factor of (2/3-epsilon), for arbitrary fixed epsilon>0. If the ratio of maximal to minimal label lengths is bounded by a constant, the approximation factor becomes (1-epsilon).

Pseudo-Convex Decomposition of Simple Polygons
	Date	Fri, 17 Mar 2006, 14:00
	Location	room SR 301
	Speaker	Stefan Gerdjikov, GeoNet-Hiwi
	Abstract	We extend a dynamic-programming algorithm of Keil and Snoeyink for finding a minimum convex decomposition of a simple polygon to the case when both con- vex polygons and pseudo-triangles are allowed. Our algorithm determines a minimum pseudo-convex decomposition of a simple polygon in O(n³) time where n is the number of the vertices of the polygon. In this way we obtain a well-structured decomposition with fewer polygons, especially if the original polygon has long chains of concave vertices.

Vergleich von Graphclusterungen
	Date	Tue, 7 Mar 2006, 11:00
	Location	room SR 315
	Speaker	Daniel Delling, Diplomarbeiter at ITI
	Abstract	Ein Ansatz zum Vergleichen von Clusterungen sind Abstandsmaße, die einen Wert von Null für zwei gleiche und von Eins für zwei maximal verschiedene Clusterungen berechnen. Ziel der Diplomarbeit war die systematische Analyse der bisherigen Maße. Dabei stellte sich heraus, dass bisherige Maße für die Abstandsmessung lediglich die Knotenmenge benutzen, was auch für den Fall, dass beide Clusterungen auf dem gleichen Graphen definiert sind, ein großer Nachteil ist. Ferner stellte sicher heraus, dass auf Clusterungen drei Arten von Abstand denkbar sind. Thema des Vortrags sind die Gliederung der Abstandsarten, die Nachteile bisheriger Maße, Erweiterungen dieser Maße, damit sie eine andere Abstandsart messen, und die Ergebnisse einiger Testreihen.

Modularity für spezielle Graphfamilien
	Date	Tue, 14 Feb 2006, 14:00
	Location	room SR -108
	Speaker	Marco Gaertler
	Abstract	Modularity ist ein Bewertungsmaß für (Graph-)Clusterungen, welches von Physikern erfunden wurde. Entsprechende waren lange einige Fragen offen, wie zum Beispiel die Berechenbarkeit oder das Verhältnis der Intuition zur Formalisierung. Inzwischen konnte gezeigt werden, dass das Entscheidungsproblem NP-vollständig ist. Im Vortrag soll nun gezeigt werden, welche Clusterintuitionen in dem Maß stecken und wie sich das Problem auf eingeschränkten Klassen (vollständige Graphen und einfache Kreise) optimal lösen lässt.

Experimentelle Analyse von Freiheitsgraden im Planar-Separator Theorem
	Date	Tue, 7 Feb 2006, 14:00
	Location	room SR -108
	Speaker	Tirdad Rahmani, Studienarbeiter at ITI Wagner
	Abstract	Klassische Formulierungen des Planar-Separator-Theorems wie die von Lipton und Tarjan lassen einer konkreten Implementierung etliche Freiheitsgrade u. a. hinsichtlich BFS-Wurzel-Auswahl und Wahl einer Nichtbaumkante, deren Einfluss auf die Separatorqualität kürzlich untersucht wurde und sich dabei als signifikant herausgestellt hat. Im Rahmen einer Studienarbeit wurden weitere Freiheitsgrade des PST, die bei der Konstruktion eines aufspannenden Baumes bzw. einer Triangulierung auftreten, evaluiert und zahlreiche Optimierungsansätze vorgestellt. Experimente konnten eine weitere deutliche Verbesserung der praktischen Performanz im Vergleich zu naiven Implementationen aufzeigen.

Richtungsbasierte Lokalisation von Sensornetzwerken
	Date	Mon, 6 Feb 2006, 13:00
	Location	room SR 236
	Speaker	Bastian Katz, Diplomarbeiter at ITI Wagner
	Abstract	Bei der Rekonstruktion der Topologie von Sensornetzen wird üblicherweise auf Entfernungsmessungen zurückgegriffen. Selbst vorhandene Algorithmen zur Richtungsgestützten Lokalisierung nutzen die Vorzüge nicht konsequent aus und bauen damit immer noch wesentlich auf das Lösen Linearer Programme. Diese Arbeit beschäftigt sich zum einen mit dem schnellen Auffinden und Auslegen maximaler eindeutig rekonstruierbarer Subgraphen, um das entsprechende Lineare Programm so weit wie möglich zu vereinfachen, und zum anderen mit einer Variante dieses Vorgehens zur Rekonstruktion auch bei fehlerbehafteten Messungen.

Modellierung und Berechnung von Wegbeschreibungen
	Date	Fri, 27 Jan 2006, 10:30
	Location	room 315
	Speaker	Frank Schulz

A Slow Approximation Algorithm for a Geometric Dispersion Problem
	Date	Fri, 20 Jan 2006, 14:00
	Location	room SR 301
	Speaker	Marc Benkert
	Abstract	We consider the problem of placing a set of discs in a region containing obstacles such that no two discs intersect. We are given a bounding polygon P and a set R of possibly intersecting unit disks whose centers are in P. The task is to find a set B of unit disks such that no disc in B intersects a disc in B u R. Finding a set B containing the maximum possible number m of unit disks is known to be NP-hard. We consider the variant of the problem, where the aim is to pack m non-intersecting discs of maximum radius, where m is as defined above. The problem has applications in computer graphics and GIS. In this paper we present a 2/3-approximation algorithm.

Minimum Cycle Basis
	Date	Mon, 16 Jan 2006, 13:00
	Location	room SR 301
	Speaker	Dorothea Wagner

Using Profiling Tools to Identify Performance Bottlenecks
	Date	Fri, 13 Jan 2006, 14:00
	Location	room SR 301
	Speaker	Thomas Willhalm

Parallele Konstruktion von Suffix-Tabellen
	Date	Fri, 23 Dec 2005, 11:00
	Location	room 315
	Speaker	Fabian Kulla, Diplomarbeiter at ITI Sanders
	Abstract	Suffix-Tabellen sind in den letzten Jahren zu einem wichtigen Instrument zur Suche in Zeichenfolgen geworden. Ohne Vorverarbeitung von Zeichenfolgen ist die benötigte Zeit zur Suche nach einem bestimmten Muster im Allgemeinen linear zur Länge der Zeichenfolge. Mit Hilfe der Suffix-Tabelle kann das Muster in logarithmischer Zeit gefunden werden. Um die benötigte Zeit zur Konstruktion der Suffix-Tabellen zu reduzieren, kann man bereits vorhandene Algorithmen auf immer schnelleren Rechnern ausführen. Diesem Vorgehen sind aber enge technische Grenzen gesetzt. Eine Alternative dazu ist die parallele Konstruktion von Suffix-Tabellen. In diesem Vortrag soll die Leistungsfähigkeit einer skalierbaren Implementierung eines parallelen Algorithmus anhand von Messungen präsentiert werden.

Textkompression mittels globaler Analyse
	Date	Tue, 20 Dec 2005, 14:00
	Location	room SR -108
	Speaker	Johannes Singler, Diplomarbeiter at ITI Sanders
	Abstract	Heutzutage verwendete Textkompressions-Verfahren beschränken die Adaption des Modells zu jedem Zeitpunkt auf einen Teil der Eingabe. Diese Selbstbeschränkung ist jedoch nicht mehr zeitgemäß, da Hauptspeicher und Rechenleistung in großen Mengen zur Verfügung stehen. In dieser Diplomarbeit wird untersucht, ob und in welchem Ausmaß die Kompressionsrate dadurch gesteigert werden kann, dass die Eingabe zunächst komplett analysiert wird, also global vorgegangen wird. Dazu werden erstens etablierte Kompressionsverfahren unter dieser neuen Rahmenbedingung studiert und modifiziert. Zweitens wird ein eigenes Verfahren vorgeschlagen, implementiert und experimentell mit etablierten Kompressoren verglichen. Dieses neue Verfahren verwendet die Datenstruktur eines Suffix-Array, um Wiederholungen gleicher Teilstücke im Text zu finden und diese durch eine Referenz auf ein bestimmtes Vorkommen zu ersetzen. Es kann Texte eigenständig komprimieren oder als Vorstufe für andere Kompressionsverfahren nutzen. Es wird aufgezeigt, dass der globale Ansatz für einige Fälle, vor allem große Dateien, eine Verbesserung der Kompressionsrate ermöglicht.

Flussmodell zum Auffinden maximaler Komponenten bei Sensorlokalisierung
	Date	Fri, 16 Dec 2005, 14:00
	Location	room SR 301
	Speaker	Bastian Katz, Diplomarbeiter at ITI Wagner

Effizientes Parsen von Bibliografiedaten
	Date	Tue, 13 Dec 2005, 14:30
	Location	room SR -108
	Speaker	Hai Wei, Hiwi at ITI Wagner
	Abstract	Zur Analyse von Literatur-, Kollaborations- oder Kozitationsnetzwerken ist oftmals mühsames Parsen von Datendumps notwendig. Gefolgt wird dies zumeist von Dingen wie manueller Säuberung, Beschränkung auf gewisse Kantengewichte, oder der Suche nach der Nachbarschaft gegebener Knoten. Es wird ein Werkzeug vorgsestellt, welches auf der Basis eines XML-Parsers und einer Datenbank aus Datendumps Graphen extrahiert. Dabei bietet das Yed-Interface viele bequeme Features zur Gestaltung des gesuchten Graphen. Bislang werden als Datenquellen Citeseer und DBLP unterstützt.

A Different Approach to the Exact Source-Target Shortest-Path Problem in Road Networks
	Date	Thu, 1 Dec 2005, 14:00
	Location	room 315
	Speaker	Kirill Müller, student at ITI Wagner
	Abstract	Many recent approaches for the source-target shortest path problem in road networks are based on Dijkstra's algorithm, e. g. ALT/REACH, Highway Hierarchies, Geometric Containers, A* goal-directed search etc. Most of them use precomputation to restrict the choice of the edges considered during search, but the search is still performed on the whole map -- which can be huge. Precomputation of all paths would allow to determine any single path in time dependent only on path length. But for huge road maps, running a simple all-pairs shortest path search would take far too long and use too much space to be useful. In 1998, Ning Jing et al. introduced a scheme for efficient APSP precomputation, storage and update, based on multi-level hierarchies. With this scheme a source-target shortest path search between any two points - no matter how far they are from each other - can be mapped to execution of a variant of Dijkstra's algorithm on a small graph and subsequent lookup of the path's course. The aim of this talk is to present an evaluation of this scheme and to show possible research topics.
	Information	[Jing et al.]

Vergleichsmaße für Clusterings
	Date	Tue, 29 Nov 2005, 14:00
	Location	room -108
	Speaker	Daniel Delling, Diplomarbeiter at ITI Wagner
	Abstract	Ein Ansatz, um zwei Clusterungen miteinander zu vergleichen und festzustellen wie verschieden bzw. ähnlich sie sind, ist der Gebrauch von Vergleichsmaßen. Wann ein Vergleichsmaß z.B. einen kleinen Abstand zweier Clusterungen ausweisen soll, kann aber von Anwendungsfall zu Anwendungsfall stark variieren. Daher ist es sinnvoll, zunächst mögliche Intuitionen für Abstände und Gleichheit zweier Clusterungen zu sammeln und zu formalisieren und aus diesen Intuitionen Regeln für Vergleichsmaße abzuleiten, um dann mögliche Vergleichsmaße zu definieren. Vorgestellt wird unsere Einteilung der Intuitionen, welcher Intuition bisherige Vergleichsmaße entsprechen und wie man diese Maße erweitern kann, damit sie andere Intuitionen repräsentieren. Desweiteren stellen wir einen neues Vergleichsmaß und erste Ergebnisse vor.

Partitionierung großer Graphen
	Date	Fri, 25 Nov 2005, 13:00
	Location	room 301
	Speaker	Karsten Sperling, Diplomarbeiter at ITI Sanders
	Abstract	Graphpartitionierung ist ein bekanntes NP-vollständiges Problem, das beispielsweise bei der Parallelisierung von gitterbasierten Simulationsmethoden oder für die Beschleunigung von Shortest-Path Algorithmen wichtige Anwendungen hat. Insbesondere beschäftigen wir uns mit der Partitionierung von Graphen mit Millionen von Knoten in tausende oder zehntausende von Stücken. Wir entwickeln einen geometrischen Partitionierungsalgorithmus, der weit bessere Ergebnisse als das klassische Recursive Coordinate Bisection Verfahren liefert. In vielen Fällen liegt der Kantenschnitt nur um 45% über dem des Multilevel-Partitionierers METIS, während die Laufzeit in Bezug auf die Anzahl der Partitionen weit besser skaliert. Weiterhin untersuchen wir METIS im Hinblick auf Effizienz und Skalierbarkeit und schlagen mehrere Verbesserungen vor.

Disjunkte kürzeste Wege in drahtlosen Sensornetzen
	Date	Tue, 22 Nov 2005, 13:30
	Location	room -108
	Speaker	Markus Maier, Diplomarbeiter at ITI Wagner
	Abstract	Drahtlose Sensornetze sind relativ störungsanfällig. Deshalb kann es sinnvoll sein, Informationen über mehrere disjunkte Wege von einem Sender zu einem Empfänger zu senden, um die Redundanz zu erhöhen. Andererseits spielen Energiebetrachtungen in drathlosen Sensornetzen eine wichtige Rolle. Die disjunkten Wege sollen deshalb möglichst energieeffizient sein. In diesem Vortrag sollen Ergebnisse zur Komplexität und Heuristiken auf allgemeinen und speziellen Graphen vorgestellt werden.

Zerlegen in konvexe Polygone
	Date	Fri, 11 Nov 2005, 13:00
	Location	room 301
	Speaker	Stefan Gerdjikov, GeoNet-Hiwi
	Abstract	Eine konvexe Zerlegung eines einfachen Polygons P ist eine Überdeckung von P mit konvexen, paarweise disjunkten Polygonen, die innerhalb von P liegen und deren Ecken Ecken von P sind. Man kann ein einfaches Polygon immer konvex zerlegen, indem man das Polygon trianguliert. Das Problem besteht jedoch darin, eine Zerlegung zu finden, die möglichst wenige konvexe Polygone benutzt. Im Seminar wird über einen Algorithmus von Keil und Snoeyink berichtet, der das Problem optimal löst.

Winkelgestützte Sensorlokalisierung
	Date	Tue, 8 Nov 2005, 14:00
	Location	room -108
	Speaker	Bastian Katz, Diplomarbeiter at ITI Wagner
	Abstract	Zu den grundlegendsten Aufgaben in Sensornetzwerken gehört die Lokalisierung der Knoten; sie ist natürlich notwendig für eine Auswertung der Daten, aber auch für geometrische Routing-Verfahren. In den meisten bisher vorgestellten Ansätzen werden neben der Modellierung als Quasi Unit Disc Graphs (QUDG) Informationen über die Entfernung miteinander kommunizierender Knoten verwendet. Obwohl technisch aufwendiger zu erlangen, ist die Kenntnis der Winkel im eingebetteten Kommunikationsgraphen der Kenntnis der Kantenlängen überlegen. Sie ermöglicht eindeutige Lokalisierung unter geringeren Voraussetzungen und effiziente Verfahren zur konsistenten Einbettung auch bei Mehrdeutigkeiten. Vorgestellt werden weiterhin Überlegungen zur Ausnutzung von Redundanz bei fehlerbehafteten Winkelmessungen.

Verfahren zur Stabilisierung des Internet-Routings
	Date	Fri, 4 Nov 2005, 14:00
	Location	room 301
	Speaker	Götz Lichtwald, TM Zitterbart
	Abstract	Die Hauptaufgabe des Internets ist die Weiterleitung von Datenpaketen. Für die Bestimmung der Route der Datenpakete von der Quelle zur Senke ist das Routing im Internet verantwortlich. Hierbei ist die Stabilität der Routen ein sehr wichtiger Aspekt, da jeder Routenwechsel Paketverluste hervorruft und dadurch die Ende-zu-Ende-Verbindung stört. Das Fast Scoped Rerouting-Verfahren hat zum Ziel die Routen des Internets zu stabilisieren, im Fehlerfall schnell eine alternative Route bereitzustellen und Auswirkungen von Fehlern zwischen Autonomen Systemen zu begrenzen. Für kurzzeitige Ausfälle/Fehler etabliert das FaSRo-Verfahren eine Umleitung und begrenzt damit die Anzahl der Routing-Kontrollnachrichten. Hierdurch wird eine Dämpfung der Routenänderungsdynamik erreicht.

Planaritätstests in Clustergraphen
	Date	Tue, 25 Oct 2005, 14:00
	Location	room -108
	Speaker	Martin Nöllenburg
	Abstract	Clustergraphen sind Graphen, für deren Knotenmenge eine hierarchische Partitionierung gegeben ist. Ziel einer planaren Zeichnung eines Clustergraphen ist nicht nur eine planare Zeichnung des zugrundeliegenden Graphen, sondern auch die Planarität der einzelnen Clusterregionen untereinander. Bisherige und neue Resultate zu Planaritätstests von Clustergraphen werden vorgestellt.

Effiziente Streaming-Algorithmen mit Min-wise Independent Permutations
	Date	Fri, 21 Oct 2005, 14:00
	Location	room 301
	Speaker	Tobias Matzner, Studienarbeiter at ITI Wagner
	Abstract	Min-wise Independent Permutations können zur effizienten Implementierung von Streaming Algorithmen eingesetzt werden. In meinem Vortrag beschreibe ich eine entsprechende Programmbibliothek und deren Optimierung sowie erste Resultate und Probleme bei deren Einsatz in einem Algorithmus zur approximativen Bestimmung der Häufigkeit von Elementen in einem Data-Stream.

Ein multidimensionaler Vergleich zwischen spektralen und kräftebasierten Layouts
	Date	Fri, 7 Oct 2005, 14:00
	Location	room 301
	Speaker	Marcus Krug, Studienarbeiter at ITI Wagner
	Abstract	Mithilfe eines auf dem Spring Embedder Layout eines Graphen beruhenden Dimensionsbegriffs wird ein empirischer Vergleich zwischen spektralen und kräftebasierten Layouts in geeigneten Räumen durchgeführt. Im Vortrag sollen die Grundlagen eines solchen Vergleichs dargelegt und die bisherigen Ergebnisse diskutiert werden.

Berechnung kürzester Wege unter Beachtung von Wegeverboten
	Date	Tue, 4 Oct 2005, 14:00
	Location	room 301
	Speaker	Kirill Müller, Studienarbeiter at ITI Wagner
	Abstract	Im Straßenverkehr wird die Bewegungsfreiheit häufig durch Abbiegeverbote eingeschränkt. Diese Arbeit untersucht, wie Kürzeste-Wege-Algorithmen erweitert werden können, so dass zwischen zwei Knoten der kürzeste Weg gefunden wird, der alle Abbiegeverbote berücksichtigt.

Summer term 2005
Einbettung von planaren Graphen mit minimalem Radius
	Date	Fri, 23 Sep 2005, 14:00
	Location	room 301
	Speaker	Étienne Schramm
	Abstract	Für einen planaren Graphen wird eine Einbettung derart gesucht, dass die Distanz zur Außenfacette minimiert wird. Hierbei seien zwei Facetten adjazent, wenn sie einen Knoten gemeinsam haben, und das Problem ist polynomiell lösbar. Dieses Problem ist mit einem anderen verwandt, nämlich der Triangulierung von planaren Graphen mit minimalem Radius oder Durchmesser.

Recoloring Proof
	Date	Fri, 9 Sep 2005, 14:00
	Location	room 301
	Speaker	Marc Benkert
	Abstract	Es wird der Beweis von Jack Snoeying vorgestellt, der es geschafft hat, die Termination unseres Recoloring-Algorithmus für unscharfe Regionen zu zeigen.

Experimentelle Analyse von Freiheitsgraden im Planar-Separator-Theorem
	Date	Tue, 30 Aug 2005, 14:00
	Location	room 301
	Speaker	Tirdad Rahmani, Studienarbeiter at ITI Wagner
	Abstract	In praktischen Anwendungen des Planar-Separator-Theorems (PST) sollen oft nicht nur die gegebenen Schranken an Separatorgröße bzw. Balanciertheit eingehalten, sondern diese beiden Größen optimiert werden. Klassische PST-Formulierungen lassen der Implementierung jedoch etliche Freiheitsgrade u. a. hinsichtlich BFS-Wurzel-Auswahl und Wahl einer Nichtbaumkante, deren Einfluss auf die Separatorqualität kürzlich untersucht wurde und sich dabei als signifikant herausgestellt hat. Im Rahmen einer Studienarbeit sollen weitere Freiheitsgrade des PST, die bei der Konstruktion eines aufspannenden Baumes bzw. einer Triangulierung auftreten, evaluiert werden. Erste Ideen dazu sollen nun in diesem Vortrag vorgestellt werden.

Generierung von Graphen mit Core-Hierarchien
	Date	Tue, 12 Jul 2005, 16:00
	Location	room 301
	Speaker	David Albrecht, Studienarbeiter at ITI Wagner

Zuordnung von Punkten mittels geometrischer Objekte
	Date	Mon, 11 Jul 2005, 14:00
	Location	room 301
	Speaker	Nikolaus Mutsanas, Diplomarbeiter at ITI Wagner

Stxxl: Standard Template Library for XXL Data Sets
	Date	Tue, 5 Jul 2005, 14:00
	Location	room 301
	Speaker	Roman Dementiev, ITI Sanders
	Abstract	In recent years, the development of theoretically I/O-efficient algorithms and data structures has received considerable attention. However much less has been done to evaluate their performance, in particular, with parallel disks or when running on large inputs with sizes that really require external memory. We present a software library Stxxl, that enables practice-oriented experimentation with huge data sets. Stxxl is an implementation of the C++ standard template library STL for external memory computations. It supports parallel disks, overlapping between I/O and computation and is the first external memory algorithm library that supports the pipelining technique that can save more than half of the I/Os. Stxxl has already been used for the following applications: implementations of external memory algorithms for computing minimum spanning trees, connected components, breadth-first search decompositions, constructing suffix arrays, and computing social network analysis metrics for huge graphs.
	Information	Stxxl homepage

Kräftebasierte Layouts und deren Eigenschaften
	Date	Fri, 1 Jul 2005, 13:45
	Location	room 301
	Speaker	Marcus Krug, Studienarbeiter at ITI Wagner

Highway Hierarchies Hasten Exact Shortest-Path Queries
	Date	Tue, 28 Jun 2005, 16:00
	Location	room 301
	Speaker	Dominik Schultes, ITI Sanders
	Abstract	We present a new speedup technique for route planning that exploits the hierarchy inherent in real world road networks. Our algorithm preprocesses the eight digit number of nodes needed for maps of the USA or Western Europe in a few hours using linear space. Shortest (i.e. fastest) path queries then take around eight milliseconds to produce exact shortest paths. This is about 2000 times faster than using Dijkstra's Algorithm.

Computational Geometry and Biology
	Date	Fri, 24 Jun 2005, 14:00
	Location	room 301
	Speaker	Prof. Dr. Sergey Bereg, University of Texas at Dallas
	Abstract	The algorithms from Computational Geometry have applications in many areas like Robotics, Geographic Information Systems, Networks and Communications, Facility Location. Computational Biology is another area where the techniques developed in Computational Geometry can be applied. Examples of the problems in biochemistry are protein docking, protein motion, collision detection, rigidity analysis of molecular graphs. We will discuss these problems and geometric approaches to solve them.

On a Memory Allocation Problem for Parallel Processors
	Date	Tue, 21 Jun 2005, 14:00
	Location	room 301
	Speaker	Rob van Stee, ITI Sanders
	Abstract	We study a memory allocation problem for parallel processors. We wish to share memory between processors in order to avoid wasting it. To minimize contention, we allow a single memory to be accessed by only two processors at a time. We give a bin packing formulation for this problem and present an algorithm which has approximation ratio 1.4.

Disjunkte kürzeste Wege in Sensornetzen
	Date	Fri, 17 Jun 2005, 14:00
	Location	room 301
	Speaker	Markus Maier, Diplomarbeiter at ITI Wagner
	Abstract	In drahtlosen Sensornetzen kann es sinnvoll sein Daten zwischen zwei Knoten auf mehrerern, disjunkten Wegen zu verschicken. Dabei ist es unter Umständen möglich, den sogenannten "Wireless Multicast Advantage" auszunutzen. Dieser entsteht dadurch, dass aufgrund der Natur des Funkmediums Nachrichten, die von einem Knoten gesendet werden, von mehreren Knoten gleichzeitig aufgefangen werden können. Durch diesen Vorteil wird das Problem eine energieoptimale Menge von disjunkten Wegen zu finden jedoch NP-schwer. Der Vortrag stellt einige Ergebnisse zur Approximation des Problems vor.

Placing Points in Sparse Regions
	Date	Wed, 25 May 2005, 10:00
	Location	room 131
	Speaker	Prof. Dr. Renï¿½van Oostrum, Universiteit Utrecht
	Abstract	We are given the following problem: let a set P of n points in a polygonal domain be given, as well as a parameter k. Our task is to place k additional points, such that the resulting set is "nicely distributed", i.e., new points should preferably be placed in sparse regions. This problem has applications in GIS and computer graphics. We give a possible formal statement of the problem, argue that is hard to solve, and take a stab at an approximation algorithm.

On the Geometric Dilation of Curved Graphs
	Date	Tue, 24 May 2005, 14:00
	Location	room 301
	Speaker	Marc Benkert
	Abstract	Eine interessante Fragestellung zur Erforschung von geometrischen Spannern ist folgende: Gegeben eine endliche Punktemenge in der Ebene, was ist der minimale Streckfaktor, den ein planarer Graph haben kann, der alle Punkte entweder als Knoten oder auf Kanten enthält? Dabei ist jede Kantenform erlaubt, solange eine differenzierbare Kurve zugrundeliegt. Ebbers-Baumann, Grüne und Klein haben gezeigt, dass jede Punktemenge in einem "Blümchenmuster"-Graph eingebettet werden kann, dessen Streckfaktor höchstens 1.678 ist. Als untere Grenze galt lange pi/2, die bestmögliche Schranke für eine Punktemenge, die auf einem Kreis eingebettet werden muss. (Streckfaktor eines Kreises: halber Kreisumfang geteilt durch Durchmesser = pi/2.) Allerdings wurde auch schon lange vermutet, dass es Punktemengen gibt, deren optimale Einbettung mehrere inzidente geschlossene Kurven enthalten muss, und dass deshalb die untere Schranke größer als pi/2 ist, da diese Kurven dann keine Kreise mehr sein können. Der Vortrag beweist dieses Ergebnis von Dumitrescu, Ebbers-Baumann, Grüne, Klein und Rote, die unter Ausnutzung eines disk-packing Resultats eine untere Schranke von pi/2 * 10^-11 zeigen konnten.

Labeling a Rectilinear Map With Sliding Labels
	Date	Fri, 20 May 2005, 14:00
	Location	room 301
	Speaker	Nikolaus Mutsanas

Konsistenz von Spektral-Clustering
	Date	Tue, 17 May 2005, 16:00
	Location	room 301
	Speaker	Dr. Ulrike von Luxburg, Fraunhofer Institut für Integrierte Publikations- und Informationssysteme, Darmstadt
	Abstract	Clustering eine Grundtechnik im Umgang mit unübersichtlichen Datenmengen. Speziell im Kontext von großen Datenmengen ist es wichtig, dass die verwendeten Clustering-Algorithmen bestimmte Konsistenz-Eigenschaften erfüllen: je mehr Datenpunkte zur Verfügung stehen, desto verläßlicher und stabiler soll die vom Algorithmus konstruierte Partition der Daten sein. Um diese Eigenschaft zu untersuchen, nimmt man an, daß die Datenpunkte zufällig gemaß einer unbekannten Verteilung aus einem Datenraum gezogen werden. Die Frage der Konsistenz besteht dann darin, die Konvergenz der konstruierten Partitionen für wachsende Stichprobengröße zu zeigen. Wir wollen die Frage der Konsistenz für die Klasse der Spektral-Clustering Algorithmen untersuchen. Spektral-Clustering benutzt Eigenvektoren der Graph-Laplace-Matrix des Ähnlichkeitsgraphs der Datenpunkte, um eine Partition der Daten zu konstruieren. Wir können zeigen, daß verschiedene Varianten von Spektral-Clustering ("normalisiert" oder "unnormalisiert") sehr verschiedene Konsistenzeigenschaften besitzen. Während die normalisierte Variante immer konvergiert, gilt Konvergenz für die unnormalisierte Variante nur unter sehr starken Zusatzbedingungen. In theoretischen und praktischen Beispielen kann man zeigen, daß diese Bedingungen in Anwendungen oft verletzt sind. Deshalb empfehlen wir, immer die normalisierte Variante des Algorithmus zu verwenden.

Lineares Programmieren — eine Übersicht
	Date	Fri, 13 May 2005, 14:00
	Location	room 301
	Speaker	Robert Görke

Visualizing Evolving Graphs by Simultaneous Embeddings
	Date	Fri, 6 May 2005, 14:00
	Location	room 301
	Speaker	Prof. Dr. Stephen Kobourov, University of Arizona
	Abstract	Traditional problems in graph visualization involve the layout of a single graph, while problems in simultaneous graph visualization involve the layout of multiple related graphs. A series of related graphs may arise from one relation between a set of objects as it evolves through time or from several relationships defined on the same set of objects. In simultaneous embedding, nodes are placed in the exact same locations in all the graphs and a series of graphs is simultaneously embeddable if it is possible to find node locations that yield straight-line crossing-free drawings for each of the individual graphs. We present polynomial-time algorithms for simultaneous embedding of various classes of planar graphs and prove that some classes of graphs cannot be simultaneously embedded. Further, we present a near-linear time algorithm for visualizing graphs that evolve through time and demonstrate its application to problems in software engineering and databases.

Geometric Duality Helps
	Date	Fri, 29 Apr 2005, 14:00
	Location	room 301
	Speaker	Alexander Wolff
	Abstract	Given a set P of points in the plane, a corridor is the region that lies between two parallel lines. We are interested in the following two corridor problems. (a) Given an integer k < n, find the narrowest corridor that contains at least k of the points in P. (b) Given a real w, find the corridor of width w that contains as many points of P as possible. It turns out that for solving these problems duality helps.

Randomized and De-Randomized Distributed Algorithms for k-Set-Cover
	Date	Tue, 26 Apr 2005, 13:15
	Location	room 301
	Speaker	Steffen Mecke

The Visibility-Voronoi Complex and its Applications
	Date	Fri, 22 Apr 2005, 14:00
	Location	room 301
	Speaker	Etienne Schramm
	Abstract	Im Bereich Motion Planning geht es oft darum, einen punktförmigen Roboter von einem Start- zu einem Zielpunkt zu bringen, ohne durch polygonale Hindernisse zu fahren. In einem zum Titel dieses Vortrags gleichnamigen Paper beschreiben die Autoren, Ron Wein, Jur van den Berg und Dan Halperin, wie man solche Wege so berechnen kann, dass sie "natürlich" aussehen, d. h. weder den Wänden zu nahe kommen noch allzu große Umwege darstellen.

Approximation Schemes for Generalized Geometric Problems
	Date	Fri, 8 Apr 2005, 14:00
	Location	room 301
	Speaker	Marc Benkert
	Abstract	Es wird Aroras Methode zum Finden eines PTAS für das Traveling Salesman Problem vorgestellt und diskutiert, auf welche geometrischen Probleme sein Ansatz verallgemeinert werden kann.

Faculty of Informatics Algorithmics I

Research Seminar

Optimisation of Clustering Algorithms for the Identification of Customer Profiles from Shopping Cart Data

Finding Important Edges for Routing in Networks

Graph-Planarisieren durch Verschieben von Knoten

Scheduling and Topology Control in Wireless Sensor Networks

Out-of-the-Box Phrase Indexing

Stabilisatorgruppen in Aut(Fz)

Design and Experimental Evaluation of A Local Graph Clustering Algorithm

Parameterized Complexity Analysis and Algorithm Design:A Natural Mission in Social Choice, Meta-Search, and Multi-Agent Systems

Effizientes Starten und Verteilen von Threads

Effiziente Tourenplanung für Pickup- und Delivery-Verkehre

Set Cover Functions für boolsche Terme oder: wieder kein Beweis für P = NP

Rainbow Sort: Sorting at the Speed of Light

Neighborhood Graphs in Clustering

Reach for A*: Fast Driving Directions on Road Networks

Load-Balancing in Web Search Engines

Contraction Hierarchies

LP-basierte Heuristiken für Graphenclusterung mit Modularity als Qualitätsmaß

Zeitexpandiertes Graphenclustern — Modellierung und Experimente

On Unfolding Lattice Chains, Trees and Polygons

Systematic Combination of Speed-Up Techniques for Exact Shortest-Path Queries

Goal-Directed Speed-Up Techniques for Shortest-Path Queries in Timetable Networks

Determination of Maximally Stable Extremal Regions in Large Images

A Node's Perspective of Changing Properties in Dynamic Networks

(Lokales) Scheduling von Übertragungen in Sensornetzen im SINR-Modell

Berechnung des Stabilisators einer Untergruppe der freien Gruppe

Parallel Highway-Node Routing

Better Approximation of Betweenness Centrality

Exakte Kreuzungsminimierung in Kreislayouts

Approximative Matchings in Cross-Match-Tests

Data Harvesting in Sensor Networks

Graphersetzung für eine Zwischendarstellung im Übersetzerbau

Verhalten und Qualität von k-Betweenness-Clusterungen

Dynamische Kürzeste-Wege-Bäume

Load-Balancing in Web Search Engines

An Optimal Bound for the MST Algorithm to Compute Energy-Efficient Broadcast Trees in Wireless Networks

Landmark Selection and Greedy Landmark-Descent Routing for Sensor Networks

MLS: An Efficient Location Service for Mobile Ad-Hoc Networks

Routing, Anycast, and Multicast for Mesh and Sensor Networks

Schnelle Berechnung von großen Matchings

Protein Domain Decomposition Using Spectral Graph Partitioning

Robuste Zentralitätsmaße in einfachen ungerichteten Graphen

Geradlinige Gitterzeichnungen planarer Graphen

Minimale Schnitte und Schnittbäume

Approximationsalgorithmen für gewichtete Matchings in Cross-Match-Tests

Efficient Data Structures Libraries

Clustern mit beschränkter Clustergröße

Survey on Internet Topology Generators on the AS Level

Minimum-Energy Reliable Paths

Allgemeine Testumgebung für das Evaluieren von Algorithmen in Java

Efficient Computation of Many-to-Many Shortest Paths

Reach for A*: an Efficient Point-to-Point Shortest-Path Algorithm

Algorithms for Metro Map Layouts

Connectivity, Realization, and Enumeration of Cover Contact Graphs

Dynamic Speed-up Techniques for Dijkstra's Algorithm

Automatische Generalisierung - aktuelle Entwicklungen, ein neues Aggregationsverfahren und offene Probleme

NP-Schwere von sektorgestützter Sensorlokalistion

DGraphML - Ein XML-basiertes Dateiformat für dynamische Graphen

Visualisierung sehr großer Graphen

Die ungarische Methode und eine geometrische Anwendung

Reporting flock patterns

Exploiting Multi-Core Parallelism in Modern Architectures

In-Memory Text Index: Abmischen von Listen

Linearzeitalgorithmus zur Vierfärbung planarer Graphen?

Verifikation von Heap-Algorithmen

Force-Directed Approaches to Sensor Localization

Kürzeste-Wege-Suche durch hierarchische Dekomposition

Schnittbasen

Discovery, Composition and Mediation of services in a Global Service – Oriented Architecture

Paging with Request Sets

A Drawing Convention for Micro/Macro Graphs

Engineering Highway Hierarchies

Correlation Clustering

Processing Huge Graphs with STXXL

Das Zirkulationsproblem - Algorithmen und Anwendungen

Enumeration of Pseudo-Cliques

Optimal Broadcast for Fully Connected Networks

Greedy Search Engine Loadbalancing

Benutzerorientierte Geovisualisierung

Parameterized Complexity Analysis and Algorithm Design:
A Natural Mission in Social Choice, Meta-Search, and Multi-Agent Systems