Finding the Sink Takes Some Time: An Almost Quadratic Lower Bound for Finding the Sink of Unique Sink Oriented Cubes

2004/03/01 by Tibor Szab�, Ingo Schurr · 1 citation
Computer Science · Mathematics · #Binary logarithm #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Computer science #Data Management and Algorithms #Discrete mathematics #Geometry #Mathematics #Oracle #Quadratic equation #Simplex #Sink (geography) #Time complexity #Upper and lower bounds #Vertex (graph theory)

paper · pdf · doi:10.1007/s00454-003-0813-8

crossref issued 2004/03/01 · crossref published 2004/03/01 · crossref published-print 2004/03/01 · openalex publication_date 2004/03/01 · crossref created 2004/03/20 · crossref deposited 2019/05/28 · crossref indexed 2025/10/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/23

Citations

• The Number Of Unique-Sink Orientations of the Hypercube*
• The Random‐Facet simplex algorithm on combinatorial cubes

Cited by

• Unique sink orientation [wikipedia]