The Complexity of Recognizing Unique Sink Orientations

DOI10.4230/LIPIcs.STACS.2015.341zbMath1355.68118OpenAlexW2240422960MaRDI QIDQ2955007

Antonis Thomas, Bernd Gärtner

Publication date: 24 January 2017

Full work available at URL: https://doi.org/10.4230/lipics.stacs.2015.341

zbMATH Keywords

complexityPSPACEcoNPunique sink orientationsrecognizing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

Generation of proper families of functions ⋮ Unique end of potential line ⋮ ONE-TO-ONE CORRESPONDENSE BETWEEN PROPER FAMILIES OF BOOLEAN FUNCTIONS AND UNIQUE SINK ORIENTATIONS OF CUBES ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unique End of Potential Line

This page was built for publication: The Complexity of Recognizing Unique Sink Orientations