Integral infeasibility and testing total dual integrality

DOI10.1016/0167-6377(91)90084-3zbMath0722.90057OpenAlexW2093283678MaRDI QIDQ757248

David L. Applegate, S. Thomas McCormick, William Cook

Publication date: 1991

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(91)90084-3

zbMATH Keywords

linear systempolyhedratotal dual integralityfeedback sets in directed graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Integer programming (90C10) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Linear systems in control theory (93C05) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

On the integral dicycle packings and covers and the linear ordering polytope, Alternatives for testing total dual integrality, A Primal-Dual Algorithm for Weighted Abstract Cut Packing, Ranking tournaments with no errors. II: Minimax relation, Ranking tournaments with no errors. I: Structural description

Cites Work

• Total dual integrality and integer polyhedra
• Finding feasible vectors of Edmonds-Giles polyhedra
• Total weak unimodularity: Testing and applications
• Matching theory
• Integer Programming with a Fixed Number of Variables
• A polynomial-time test for total dual integrality in fixed dimension
• Polynomial Algorithms for Totally Dual Integral Systems and Extensions
• A generalization of max flow—min cut
• A Minimax Theorem for Directed Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item