Integral infeasibility and testing total dual integrality

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

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

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 system; polyhedra; total dual integrality; feedback sets in directed graphs

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

52B12: Special polytopes (linear programming, centrally symmetric, etc.)

90C10: Integer programming

68R10: Graph theory (including graph drawing) in computer science

90C27: Combinatorial optimization

93C05: Linear systems in control theory

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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