On the integral dicycle packings and covers and the linear ordering polytope

DOI10.1016/0166-218X(94)00060-QzbMath0826.05047MaRDI QIDQ1894372

Michal Penn, Zeev Nutov

Publication date: 24 July 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

digraphinequalitypolytopeconvex hullintegral dicycle coverintegral dicycle packingacyclic tournamentslinear ordering polynomial

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Linear programming (90C05) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Directed graphs (digraphs), tournaments (05C20)

Related Items

A survey on the linear ordering problem for weighted or unweighted tournaments, On non-\(\{0,{1\over 2},1\}\) extreme points of the generalized transitive tournament polytope, Packing directed cycles efficiently, An updated survey on the linear ordering problem for weighted or unweighted tournaments, A branch and bound algorithm for the minimum storage-time sequencing problem, Doubly stochastic matrices and dicycle covers and packings in Eulerian digraphs

Uses Software

• LOLIB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Random utility representation of binary choice probabilities: A new class of necessary conditions
• Integral infeasibility and testing total dual integrality
• The ellipsoid method and its consequences in combinatorial optimization
• A game-theoretic approach to the binary stochastic choice problem
• Geometric algorithms and combinatorial optimization
• A necessary but insufficient condition for the stochastic binary choice problem
• A note on small linear-ordering polytopes
• A Minimax Theorem for Directed Graphs
• Compositions of Graphs and Polyhedra IV: Acyclic Spanning Subgraphs
• Permutation Polyhedra