The complexity of recognizing unique sink orientations

DOI10.4230/LIPICS.STACS.2015.341MaRDI QIDQ2955007zbMATH OpenOpenAlexFDO

Authors Antonis Thomas, B. 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)

Recommendations

• Mathematical Foundations of Computer Science 2004
• Counting unique-sink orientations
• One-to-one correspondense between proper families of Boolean functions and unique sink orientations of cubes
• Unique sink orientations of grids
• On the complexity of determining whether there is a unique Hamiltonian cycle or path

Cited in

(9)

• scientific article; zbMATH DE number 1947444 (Why is no real title available?)
• On flipping edge sets in unique sink orientations
• The complexity of all-switches strategy improvement
• Unique End of Potential Line
• Unique end of potential line
• Generation of proper families of functions
• Two choices are enough for P-LCPs, USOs, and colorful tangents
• Exponential lower bounds for history-based simplex pivot rules on abstract cubes
• One-to-one correspondense between proper families of Boolean functions and unique sink orientations of cubes

This page was built for publication: The complexity of recognizing unique sink orientations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2955007)