The negative cycles polyhedron and hardness of checking some polyhedral properties

DOI10.1007/s10479-010-0690-5zbMath1225.90143OpenAlexW1997609492WikidataQ59560546 ScholiaQ59560546MaRDI QIDQ646701

Endre Boros, Hans Raj Tiwary, Khaled M. Elbassioni, Vladimir A. Gurvich

Publication date: 17 November 2011

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-010-0690-5

zbMATH Keywords

enumeration problemextreme directiondirected graphvertexhardness of approximationnegative cycles0/1-polyhedronflow polytopehalf-integral polyhedramaximum support

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Boolean programming (90C09)

Related Items (6)

Unnamed Item ⋮ Enumerating Minimal Transversals of Hypergraphs without Small Holes ⋮ Efficient geometric operations on convex polyhedra, with an application to reachability analysis of hybrid systems ⋮ Enumerating Vertices of Covering Polyhedra with Totally Unimodular Constraint Matrices ⋮ Enumerating Vertices of 0/1-Polyhedra associated with 0/1-Totally Unimodular Matrices ⋮ Forbidden Vertices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of recognizing linear systems with certain integrality properties
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• The vertex set of a \(0/1\)-polytope is strongly \(\mathcal P\)-enumerable
• Primal-dual methods for vertex and facet enumeration
• Efficient enumeration of the vertices of polyhedra associated with network LP's
• How good are convex hull algorithms?
• A polyhedron with all \(s-t\) cuts as vertices, and adjacency of cuts
• Reverse search for enumeration
• On recognizing integer polyhedra
• Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
• Automata, Languages and Programming
• Generating all vertices of a polyhedron is hard

This page was built for publication: The negative cycles polyhedron and hardness of checking some polyhedral properties