Counting unique-sink orientations

DOI10.1016/J.DAM.2013.07.017MaRDI QIDQ2434730zbMATH OpenOpenAlexFDO

Authors Jan Foniok, B. Gärtner, Lorenz Klaus, Markus Sprecher

Publication date 7 February 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1012.1573

zbMATH Keywords

K-matrixlinear complementarity problemP-matrixpivotingunique-sink orientation

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10) Linear programming (90C05)

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.

Recommendations

• Mathematical Foundations of Computer Science 2004
• The number of unique-sink orientations of the hypercube
• Unique sink orientations of grids
• Unique Sink Orientations of Grids
• Deterministic algorithms for unique sink orientations of grids

Cites work

• A Partition Theorem for Euclidean n-Space
• A polynomial-time algorithm for the tridiagonal and Hessenberg P-matrix linear complementarity problem
• Digraph Models of Bard-Type Algorithms for the Linear Complementarity Problem
• Finding the sink takes some time: An almost quadratic lower bound for finding the sink of unique sink oriented cubes
• Geometric Properties of Hidden Minkowski Matrices
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 53115 (Why is no real title available?)
• scientific article; zbMATH DE number 192986 (Why is no real title available?)
• Linear complementarity problems solvable by a polynomially bounded pivoting algorithm
• Linear complementarity problems solvable by A single linear program
• Linear programming and unique sink orientations
• Lower Bounds for Approximation by Nonlinear Manifolds
• LP-orientations of cubes and crosspolytopes
• NP-completeness of the linear complementarity problem
• On Dedekind's Problem: The Number of Monotone Boolean Functions
• Pivoting in linear complementarity: Two polynomial-time cases
• Randomized pivot algorithms for \(P\)-matrix linear complementarity problems
• The number of unique-sink orientations of the hypercube
• THE SMALLEST ENCLOSING BALL OF BALLS: COMBINATORIAL STRUCTURE AND ALGORITHMS
• Unique sink orientations of grids

Cited in

(12)

• A complexity analysis of policy iteration through combinatorial matrices arising from unique sink orientations
• The number of unique-sink orientations of the hypercube
• The complexity of recognizing unique sink orientations
• Unique Sink Orientations of Grids
• Enumeration of PLCP-orientations of the 4-cube
• Exponential lower bounds for history-based simplex pivot rules on abstract cubes
• Mathematical Foundations of Computer Science 2004
• Realizability makes a difference: a complexity gap for sink-finding in USOs
• Realizability in Matoušek unique sink orientations: characterization and complexity gap
• On the existence of Hamiltonian paths for history based pivot rules on acyclic unique sink orientations of hypercubes
• On degeneracy in the P-matroid oriented matroid complementarity problem
• Unique sink orientations of grids

Describes a project that uses

Uses Software

• Miniball

This page was built for publication: Counting unique-sink orientations

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