Article ID: | iaor19921076 |
Country: | Netherlands |
Volume: | 10 |
Issue: | 7 |
Start Page Number: | 377 |
End Page Number: | 382 |
Publication Date: | Oct 1991 |
Journal: | Operations Research Letters |
Authors: | Gerards A.M.H. |
Keywords: | programming: linear |
The paper extends a result of Barahona, saying that T-join and perfect matching problems for planar graphs can be formulated as linear programming problems using a polynomial number of constraints and variables, to graphs embeddable on an arbitrary, but fixed, surface.