scientific article
From MaRDI portal
zbMath0565.90044MaRDI QIDQ3680606
Martin Grötschel, Michael Jünger, Gerhard Reinelt
Publication date: 1985
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
computational complexityNP-hardlinear ordering problemcutting plane algorithmacyclic subdigraph problemfacet structure of polytopes
Integer programming (90C10) Directed graphs (digraphs), tournaments (05C20) Polytopes and polyhedra (52Bxx)
Related Items
\((0,{1\over 2},1)\) matrices which are extreme points of the generalized transitive tournament polytope, On the integral dicycle packings and covers and the linear ordering polytope, Vertices of the generalized transitive tournament polytope, On non-\(\{0,{1\over 2},1\}\) extreme points of the generalized transitive tournament polytope, *-graphs of vertices of the generalized transitive tournament polytope, An Exact Method for the Minimum Feedback Arc Set Problem, A branch-and-bound algorithm to solve the linear ordering problem for weighted tournaments, Weak order polytopes., On approximability of linear ordering and related NP-optimization problems on graphs., The feedback arc set problem with triangle inequality is a vertex cover problem, Induced binary probabilities and the linear ordering polytope: A status report, Transitive packing, Generalized transitive tournaments and doubly stochastic matrices, An updated survey on the linear ordering problem for weighted or unweighted tournaments, Determining the automorphism group of the linear ordering polytope, Doubly stochastic matrices and dicycle covers and packings in Eulerian digraphs
Uses Software
