Counting Unique-Sink Orientations

Abstract

Unique-sink orientations (USOs) are an abstract class of orientations of the n-cube graph. We consider some classes of USOs that are of interest in connection with the linear complementarity problem. We summarise old and show new lower and upper bounds on the sizes of some such classes. Furthermore, we provide a characterisation of K-matrices in terms of their corresponding USOs.

13 pages; v2: proof of main theorem expanded, plus various other corrections. Now 16 pages; v3: minor corrections

References in corpus (1)

• Pivoting in Linear Complementarity: Two Polynomial-Time Cases

Cited by in corpus (3)

• A New Combinatorial Property of Geometric Unique Sink Orientations
• A Strongly Polynomial Reduction for Linear Programs over Grids
• A Quantum Approach to the Unique Sink Orientation Problem