Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, April 05, 2007, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Penny Haxell (Univ. of Waterloo)
Let $G$ be a graph with a distinguished vertex $d$. Suppose that each vertex of $G$ has a preference list of a set of paths joining it to $d$. A solution to the stable paths problem is a tree $T$ in $G$ rooted at $d$, with the property that for each vertex $x$, if $x$ prefers some path $P$ to the path from $x$ to $d$ in $T$, then some edge of $P$ not incident to $x$ is missing from $T$. Not every instance of the stable paths problem has a solution, but we show that every instance does have a fractional solution.
Automatic MiSe System Software Version 1.4803M | admin login