|
Fr, 22.10.2004, 10:00 Uhr s.t.
|
|
|
Mi, 27.10.2004
|
Moritz Maaß
Fault-Tolerant Text Indexing
|
|
In this talk we address the problem of constructing
an index for a text document or a collection of
documents to answer various questions about the
occurrences of a pattern when allowing a constant
number of errors. In particular, our index can be
built to report all occurrences, all positions, or
all documents where a pattern occurs in time linear
in the size of the query string and the number of
results. This improves over previous work where the
lookup time always depended upon the size of the
document corpus. Our data structure has size
O( n log^k n) on average and with high
probability for input size n and queries with up
to k errors. Additionally, we present a trade-off
between query time and index complexity that
achieves worst-case bounded index size and
preprocessing time with linear lookup time on
average.
This is joint work with
Johannes Nowak
|
|
|
Mi, 3.11.2004
|
Sven Kosub
Implementierung kürzester Wege
|
|
Im Internet erfolgt die Koordination des Verhaltens von
Entitäten (wie Routern, Servern etc.), die von verschiedenen
Parteien kontrolliert werden, durch Protokolle. Unter der Annahme, dass
die Parteien ihren eigenen Interessen folgen, ist davon auszugehen, dass
Protokolle nicht ohne weiteres Zutun eingehalten werden - insbesondere
nicht, wenn es für eine Partei von Vorteil ist zu "lügen". Der
Protokollentwurf muss deshalb durch geeignete Anreizsysteme flankiert
sein, um ein system- und zielkonformes Verhalten zu ermöglichen.
Das allgemeine Standardverfahren der Implementierungstheorie ist hierbei
der VCG-Mechanismus, der die Parteien durch Seitenzahlungen anregt, ihre
wahren Präferenzen zu offenbaren. Im Zentrum dieses
Übersichtsvortrages steht das Implementierungsproblem, in einem
Netzwerk einen kürzesten Weg zu bestimmen, wobei die Kanten
(Verbindungen) im Besitz von Parteien sind. Wie teuer kann es werden,
einen solchen Pfad zu finden? Zur Beantwortung dieser Frage geben wir
zunächst eine kurze, systematische Einführung in die
Implementierungstheorie und diskutieren anschließend Arbeiten und
Ergebnisse zur Implementierung des Kürzeste-Wege-Problems.
|
|
|
Mi, 17.11.2004
|
Sebastian Wernicke
Fixed Parameter Tractability of Vertex Bipartization
|
|
In a recent breakthrough paper (2.5 pages containing one Lemma),
B. Reed, K. Smith and A. Vetta give an O(4^k * n^O(1)) algorithm
for the Vertex Bipartization problem. While the result itself is
quite astounding, the algorithmic technique of inductive compression
used in the paper seems useful for settling the fixed-parameter
tractability of an even wider range of problems.
|
|
|
Mi, 1.12.2004
|
Dmytro Chibisov
Towards the Efficient Method for Collision-Free Motion Planning
|
(joint work with E. W. Mayr and S. Pankratov)
The talk discusses a number of computational tasks arising
in the calculation of the collision-free motion of a geometric
object avoiding collisions with obstacles of a particular shape.
The object to be moved as well as obstacles are semi-algebraic
sets represented as logical conjunction of polynomial inequalities.
According to configuration space approach, the object to be
moved is replaced by an individual point in the so-called
configuration space. The calculation of forbidden configurations,
due to the presense of obstacles, can be reduced to the calculation
of projection of semi-algebraic sets. We shall show how the projection
can be calculated by quantifier elimination over the reals.
In this way the problem is reduced to the calculation of the
motion of an individual point in the configuration space.
We also show how the collision-free motion in the configuration space
can be modeled with the help of the Newton's equations,
which can be solved numerically in an efficient manner.
|
|
|
Mi, 15.12.2004
|
Seth
Pettie, MPI Saarbrücken
Approximating Shortest Paths with Purely Additive Spanners
|
An additive k-spanner of a graph is a subgraph whose distance metric
approximates that of the original graph to within an additive error of
k. (Graphs are undirected and unweighted). It is known that every graph
contains an additive 2-spanner with O(n^{3/2}) edges and that this bound
is optimal. Until the present work no other additive spanners were
known and their existence was very much in doubt.
In this talk I'll discuss a new method for computing additive spanners
based on an economics inspired view of the problem. Our primary result
is that every graph contains an additive 6-spanner with O(n^{4/3}) edges.
The same method is used to prove several lesser results.
|
|
Do,
16.12.2004, 14:00 Uhr s.t.
|
Irit Katriel, MPI Saarbrücken
Online Topological Ordering
|
|
It is shown that the problem of maintaining the topological order
of the nodes of a directed acyclic graph
while inserting m edges can be solved
in O(min {m^(3/2) log n,m^(3/2)+n^2 log n} ) time, an
improvement over the best known result of O(mn).
In addition, we analyze the complexity of the same algorithm with
respect to the treewidth k of the underlying undirected graph. We show
that the algorithm runs in time O(m k log^2 n) for general k and
that it can be implemented to run in O(n log n) time on trees, which
is optimal. If the input contains cycles, the algorithm detects this.
This talk described joint work with Hans L. Bodlaender.
|
|
|
Mi, 22.12.2004
|
Markus Holzer
Reflections on REFLEXION - Computational Complexity Considerations
on a Puzzle Game
|
|
We investigate the complexity of solving puzzles in the game
REFLEXION. It is shown that the difficulty of the puzzles depends
critically on the features used in the puzzles; the most basic
variant of the game is SL-complete, and hence can be solved in
polynomial time, whereas other variants are NP- or even
PSPACE-complete. This paper is a joint work with S. Schwoon
(Universit"at Stuttgart).
|
|
|
Mi, 26.1.2005
|
Markus Holzer
Flip-Pushdown Automata: k+1 Pushdown Reversals are Better Than k
|
|
Flip-pushdown automata are pushdown automata with
the additional power to flip or reverse its
pushdown, and were recently introduced by Sarkar
(2001). We solve most of Sarkar's open problems. In
particular, we show that k+1 pushdown reversals
are better than k for both deterministic and
nondeterministic flip-pushdown automata, i.e., there
are languages which can be recognized by a
deterministic flip-pushdown automaton with k+1
pushdown reversals but which cannot be recognized by
a k-flip-pushdown (deterministic or
nondeterministic). Furthermore, we investigate
closure and non-closure properties as well as
computational complexity problems such as fixed and
general membership. The presented results are from
joint works with Martin Kutrib (Universität
Gießen).
|
|
