 Do,31.5.2001, 17:00
|
Catherine Greenhill (University of Melbourne)
Hamiltonian decompositions of random bipartite regular graphs
|
|
A random d-regular graph on n vertices
a.a.s. has an edge-decomposition into Hamilton
cycles, when d is an even constant. (Here
a.a.s. means `asymptotically almost surely';
i.e. with probability tending to 1 as n
tends to infinity). Kim and Wormald proved
this using the small subgraph
conditioning method. Recently, Kim, Wormald
and I proved the corresponding result for
random bipartite regular graphs, using
the same method. Perhaps surprisingly, the
result is harder to prove for bipartite
graphs. Two critical quantities needed for
the proof are analysed using the
differential equations method.
|
|
|
Mi,13.6.2001
|
Thomas Bayer
Formgedächtnismaterialien und Computeralgebra
|
|
When modeling shape memory alloys one has to construct a free energy
$\Phi(F,\theta)$
which has to assume global minima on various strata of the orbit space
of the
symmetry group $G$ depending on the temperature $\theta$.
We provide an algorithm for decomposing a $G-$variety ($G$ finite) $X$
and its
orbit space $Z = X/G$ in different strata, each corresponding to a
different
orbit type. An application to the construction of $\Phi$ for
Nickel-Titanium alloys
is presented.
|
|
|
Mi,20.6.2001
|
Barbara König
Analyse von Graphtransformations-Systemen
|
Graphtransformations-Systeme sind im allgemeinen Turing-maechtig und
daher sind automatischen Verifikationsverfahren nicht anwendbar. Es
ist allerdings moeglich, Graphtransformation-Systeme mit Hilfe von
sogenannten Petri-Graphen (einer Kombination aus Graphen und
Petri-Netzen) zu approximieren, die die erreichbaren Graphen und die
moeglichen Zustandsuebergaenge nach oben und unten abschaetzen.
In dem Vortrag wird behandelt, wie man solche Approximationen aus
Graphtransformations-Systemen, gegeben durch einen Startgraph und
einer Menge von Regeln, ableiten kann und mit welchen Methoden man aus
ihnen Informationen extrahieren kann.
Eine solche Methoden ist es, einen Petri-Graph als endlichen
Automaten zu betrachten und damit die Menge aller moeglichen Wege
durch erreichbare Graphen abzuschaetzen. Ausserdem wird untersucht,
welche praedikatenlogischen Formeln auf Graphen die Eigenschaft haben,
dass aus ihrer Gueltigkeit fuer die Approximation auch die Gueltigkeit
fuer das eigentliche System folgt.
|
|
|
Mi,27.6.2001
|
Mark Scharbrodt
Competitive analysis in stochastic scheduling: A new approach to
average case analysis
|
|
We propose a new approach for analysing the performance
of scheduling algorithms: The average case competitive analysis.
With the problem of minimizing the total sum of completion times on parallel
machines we show how this analysis yiedls new insights into
stochastic scheduling policies. We show that, given a simple LIST--rule,
the expected competitive ratio is a constant independent on the
number of jobs. In contrast, the worst case ratio grows linearly with the
number of jobs. We use sophisticated proof techniques that use concentration
results and carefully deal with jobs that do not behave as expected. In that
way we provide an in--depth investigation of the strategy's performace space.
|
|
|
Mo,2.7.2001, 17:15
|
|
|
Mi,4.7.2001
|
Martin Raab
Gröbnerbasen, torische Ideale und Matroide
|
|
In diesem Vortrag wird gezeigt, wie man
Methoden aus der Computeralgebra auf die
ganzzahlige lineare Programmierung anwenden
kann. Für die in diesem Zusammenhang
betrachteten Ideale können
Gröbnerbasen in polynomiellem Platz
berechnet werden. Um Aussagen über die
Struktur dieser Gröbnerbasen zu erhalten,
betrachten wir das Optimierungsproblem auf
Matroiden und Schnitten von Matroiden.
|
|
|
Mi,11.7.2001
|
Denis Therien (derzeit Uni Tübingen, ansonst Uni McGill,
Montreal)
Definability of regular languages in first-order logic
|
|
First-order logic offers a convenient framework to
describe regular languages. I will present old and new results
about the model: in particular, deep connections with algebra
will be emphasized and shown to often yield decision procedures
to test if a language is expressible within a given class of formulas.
Interesting open questions will also be discussed.
|
|
|
Do,19.7.2001, 13:00
|
Michal Mnuk
Grapheneigenschaften, Polynomideale und Färbbarkeit
|
|
Mehrfache Beschreibung von mathematischen Objekten mit verschiedenen
Mitteln führt oft zur Verbesserung des Verständnisses für innere
Zusammenhänge. Im Vortrag wird eine Methode zur Repräsentierung von
Grapheneigenschaften durch Polynomideale vorgestellt. Es werden
Vorteile, aber auch inhärente Einschränkungen diskutiert. Anschließend
wird gezeigt, wie diese Methode beim Studium der Färbbarkeit von
Graphen verwendet werden kann.
|
|
|
Mi,25.7.2001
|
Peter Rossmanith
Exact Solutions for Closest String and Related Problems
|
|
Closest String is one of the core problems in the field of
consensus word analysis with particular importance for computational
biology. Given k strings of same length and a positive integer d, find
a "closest string" such that none of the given strings has Hamming
distance greater than d from s. Closest String is NP-complete. In
biological practice, however, d usually is very small. We show how to
solve Closest String in linear time for constant d (the exponential
growth in d is bounded by (2d)^d). We extend this result to the closely
related problems d-Mismatch and Distinguishing String Selection.
Moreover, we give a linear time algorithm for Closest String when k = 3
and d is arbitrary. Finally, the practical usefulness of our findings
is substantiated by some experimental results.
|
|
|
