Deterministic algorithms for unique sink orientations of grids

DOI10.1007/978-3-319-42634-1_29MaRDI QIDQ2817878zbMATH OpenOpenAlexFDO

Authors Malte Milatz, Jerri Nummenpalo, Antonis Thomas, 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

LP-type problemunique sink orientationviolator spaces

Mathematics Subject Classification ID

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

Recommendations

• Unique sink orientations of grids
• Unique Sink Orientations of Grids
• The complexity of optimization on grids
• Finding the sink takes some time: An almost quadratic lower bound for finding the sink of unique sink oriented cubes
• scientific article; zbMATH DE number 1947444

Cites work

• A subexponential bound for linear programming
• Algorithms – ESA 2005
• Deterministic Algorithms for 2-d Convex Programming and 3-d Online Linear Programming
• Dynamic programming with convexity, concavity and sparsity
• Entering and leaving \(j\)-facets
• Geometric applications of a matrix-searching algorithm
• Grid orientations, \((d,d+2)\)-polytopes, and arrangements of pseudolines
• scientific article; zbMATH DE number 1241841 (Why is no real title available?)
• scientific article; zbMATH DE number 1962814 (Why is no real title available?)
• Improved deterministic algorithms for linear programming in low dimensions
• On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
• One line and n points
• Unique sink orientations of grids
• Violator spaces: Structure and algorithms

Cited in

(8)

• Finding the sink takes some time: An almost quadratic lower bound for finding the sink of unique sink oriented cubes
• The complexity of optimization on grids
• Counting unique-sink orientations
• Unique Sink Orientations of Grids
• scientific article; zbMATH DE number 1947444 (Why is no real title available?)
• The niceness of unique sink orientations
• On the existence of Hamiltonian paths for history based pivot rules on acyclic unique sink orientations of hypercubes
• Unique sink orientations of grids

This page was built for publication: Deterministic algorithms for unique sink orientations of grids

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