The negative cycles polyhedron and hardness of checking some polyhedral properties
type: Item
instance of: scholarly article
title: The negative cycles polyhedron and hardness of checking some polyhedral properties
zbMATH Open document ID: 1225.90143
author: Endre Boros
author: Hans Raj Tiwary
author: Khaled Elbassioni
author: Vladimir Gurvich
published in: Annals of Operations Research
publication date: 2011-11-17T00:00:00Z
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C09
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 5973857
zbMATH Keywords: flow polytope
zbMATH Keywords: 0/1-polyhedron
zbMATH Keywords: vertex
zbMATH Keywords: extreme direction
zbMATH Keywords: enumeration problem
zbMATH Keywords: negative cycles
zbMATH Keywords: directed graph
zbMATH Keywords: half-integral polyhedra
zbMATH Keywords: maximum support
zbMATH Keywords: hardness of approximation
MaRDI profile type: Publication
full work available at URL: s10479-010-0690-5
OpenAlex ID: W1997609492
Wikidata QID: Q59560546
cites work: Q4452091
cites work: A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
cites work: Reverse search for enumeration
cites work: How good are convex hull algorithms?
cites work: Automata, Languages and Programming
cites work: Primal-dual methods for vertex and facet enumeration
cites work: The vertex set of a \(0/1\)-polytope is strongly \(\mathcal P\)-enumerable
cites work: The complexity of recognizing linear systems with certain integrality properties
cites work: A polyhedron with all \(s-t\) cuts as vertices, and adjacency of cuts
cites work: Generating all vertices of a polyhedron is hard
cites work: On recognizing integer polyhedra
cites work: Efficient enumeration of the vertices of polyhedra associated with network LP's
cites work: Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
cites work: Q3818127
cites work: Q4782696
DOI: 10.1007/S10479-010-0690-5
description: scientific article; zbMATH DE number 5973857