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

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

• People
  • Personnel
  • Guests
  • Alumni
• Reports
  • Current Report
  • Report for 2023
  • Report for 2022
  • Previous Reports
• Research
  • Grants
  • Dissertations
  • Master/Bachelor Theses
  • Current Publications
  • Previous Publications
• Mittagsseminar
• Courses
• Thesis Topics
• Events
  • Workshops
    • Current
    • Previous
  • Social
    • SOLA
    • GREBGE
• 

Towards The Peak - Problem Section

Finding The Sink Against The Devil

presented by Komei Fukuda

Given any orientation we aim to find either a sink or a certificate that the orientation does not have the unique sink property. The certificate should be of polynomial size, e.g. two vertices v,w with out-map s(v),s(w), such that $(s(v)\oplus s(w))\cap(v\oplus w)=\emptyset$.

Denote by D(d) the minimal number of steps a deterministic algorithm would need for this problem and by t(d) the minimal number of steps a deterministic algorithm needs to find the sink in a unique sink orientation. It is obvious that $t(d)\leq D(d)$. For the dimensions 1,2 and 3 we have equality.

Imprint Disclaimer Copyright