Unique sink orientations of grids

DOI10.1007/s00453-007-9090-xzbMath1203.68124OpenAlexW2070970096MaRDI QIDQ930596

Walter D. jun. Morris, Leo Rüst, Bernd Gärtner

Publication date: 1 July 2008

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/20.500.11850/14390

zbMATH Keywords

linear programminggeneralized linear complementarity problemHolt-Klee conditionsink finding algorithmunique sink orientation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

A Mihalisin-Klee theorem for fans ⋮ Pivoting in linear complementarity: Two polynomial-time cases ⋮ Directed random walks on polytopes with few facets ⋮ Realizability makes a difference: a complexity gap for sink-finding in USOs ⋮ Counting unique-sink orientations ⋮ Enumeration of PLCP-orientations of the 4-cube ⋮ Unnamed Item ⋮ Random Walks on Polytopes of Constant Corank ⋮ Improved bound on the worst case complexity of policy iteration ⋮ Efficient computation of a canonical form for a matrix with the generalized P-property ⋮ Deterministic Algorithms for Unique Sink Orientations of Grids ⋮ On the Holt-Klee property for oriented matroid programming ⋮ The complexity of optimization on grids

Uses Software

• Miniball
• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Existence theory and \(Q\)-matrix characterization for the generalized linear complementarity problem: Revisited
• Puzzles and polytope isomorphisms
• Completely unimodal numberings of a simple polytope
• A simple way to tell a simple polytope from its graph
• Small-dimensional linear programming and convex hulls made easy
• Linear programming, the simplex algorithm and simple polytopes
• Automata, logics, and infinite games. A guide to current research
• A subexponential randomized algorithm for the simple stochastic game problem
• Existence theory and \(Q\)-matrix characterization for the generalized linear complementarity problem
• Signable posets and partitionable simplicial complexes
• A subexponential bound for linear programming
• Grid orientations, \((d,d+2)\)-polytopes, and arrangements of pseudolines
• Linear programming and unique sink orientations
• Jumping Doesn’t Help in Abstract Cubes
• On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
• Long Monotone Paths in Abstract Polytopes
• Polynomial algorithms in linear programming
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• Digraph Models of Bard-Type Algorithms for the Linear Complementarity Problem
• Lower bounds for a subexponential optimization algorithm
• Lectures on Polytopes
• Las Vegas algorithms for linear and integer programming when the dimension is small
• One line and n points
• The Random‐Facet simplex algorithm on combinatorial cubes
• Linear programming — Randomization and abstract frameworks
• A Linear Complementarity Problem with a P-Matrix
• LP-orientations of cubes and crosspolytopes
• THE SMALLEST ENCLOSING BALL OF BALLS: COMBINATORIAL STRUCTURE AND ALGORITHMS
• Mathematical Foundations of Computer Science 2004
• Fundamentals of Computation Theory
• A generalization of the linear complementarity problem