A Polynomial Time Algorithm for Solving Systems of Linear Inequalities with Two Variables Per Inequality

DOI10.1137/0209063zbMath0447.68036OpenAlexW2073873127MaRDI QIDQ3893299

Bengt Aspvall, Yossi Shiloach

Publication date: 1980

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0209063

zbMATH Keywords

algorithmpolynomial timelinear inequalitiesmechanical verificationrandom access machine

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05)

Related Items (10)

The Linear Complementarity Problems with a Few Variables per Constraint ⋮ A set partitioning reformulation of a school bus scheduling problem ⋮ Incremental closure for systems of two variables per inequality ⋮ Temporal constraint networks ⋮ A simple GAP-canceling algorithm for the generalized maximum flow problem ⋮ Bargaining dynamics in exchange networks ⋮ Automatic inference of determinacy and mutual exclusion for logic programs using mode and type analyses ⋮ Minimum cost stability in exchange networks ⋮ Stabilizing Weighted Graphs ⋮ A class of polynomially solvable range constraints for interval analysis without widenings

This page was built for publication: A Polynomial Time Algorithm for Solving Systems of Linear Inequalities with Two Variables Per Inequality