Deterministic Algorithms for Unique Sink Orientations of Grids

DOI10.1007/978-3-319-42634-1_29zbMath1476.68191OpenAlexW2485187644MaRDI QIDQ2817878

Antonis Thomas, Malte Milatz, Jerri Nummenpalo, Luis Barba

Publication date: 2 September 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-42634-1_29

zbMATH Keywords

violator spacesLP-type problemunique sink orientation

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20) Randomized algorithms (68W20) Graph operations (line graphs, products, etc.) (05C76)

Related Items

The complexity of optimization on grids

Cites Work

• Unnamed Item
• Unnamed Item
• Unique sink orientations of grids
• Violator spaces: Structure and algorithms
• Geometric applications of a matrix-searching algorithm
• Dynamic programming with convexity, concavity and sparsity
• A subexponential bound for linear programming
• Grid orientations, \((d,d+2)\)-polytopes, and arrangements of pseudolines
• On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
• Deterministic Algorithms for 2-d Convex Programming and 3-d Online Linear Programming
• One line and n points
• Improved Deterministic Algorithms for Linear Programming in Low Dimensions
• Algorithms – ESA 2005
• Entering and leaving \(j\)-facets