The complexity of recognizing unique sink orientations

DOI10.4230/LIPICS.STACS.2015.341zbMATH Open1355.68118OpenAlexW2240422960MaRDI QIDQ2955007FDOQ2955007

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

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

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)

Cited In (7)

• Title not available (Why is that?)
• The complexity of all-switches strategy improvement
• Unique End of Potential Line
• Unique end of potential line
• Generation of proper families of functions
• 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)