Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

i-Niceness

Towards The Peak - Problem Section

next up previous
Next: Bounds For Random Edge Up: Problem Section Previous: Almost Uniform Sampling of

i-Niceness

presented by Emo Welzl

Given a unique sink orientation $\phi$ and a vertex v, the reachmap r(v) of v is the set of all edge-labels such that for every $i\in r(v)$there is a directed path starting in v and containing an edge of label i. More formally,

\begin{displaymath}r(v)=s(v)\cup\bigcup\{r(w)\vert\mbox{$w$ successor of $v$}\}.\end{displaymath}

Call a unique sink orientation i-nice, if for every vertex v there is a vertex w with distance at most i from v and $r(w)\subsetneq r(v)$. Since there is always a path from a vertex v to the sink of the cube, the sink is in the subcube generated by v and the directions in r(v). Therefore RANDOM EDGE on an i-nice unique sink orientation will take an expected number of at most di steps.

Clearly every unique sink orientation of dimension d is d-nice. Can we do better? In particular what is the general niceness of acyclic unique sink orientations?

In dimension three every acyclic unique sink orientation is 1-nice except the orientation one gets by reorienting the cyclic unique sink orientation, which is 2-nice.


Ingo Schurr and Uli Wagner ({schurr,uli}@inf.ethz.ch)
2001-09-04