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

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Summary

Towards The Peak - Problem Section

next up previous
Next: Almost Uniform Sampling of Up: Finding The Sink Against Previous: The Fibonacci-Seesaw Also Works

Summary

Nearly all known algorithms for finding the sink in a unique sink orientation can produce a certificate after some minor modification. Only in dimension four it is not clear whether an algorithm can produce a certificate or a sink in 7 steps or not. The question remains if t(d)=D(d).


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