On cuts and matchings in planar graphs

On cuts and matchings in planar graphs

0.00 Avg rating0 Votes
Article ID: iaor19941869
Country: Netherlands
Volume: 60
Issue: 1
Start Page Number: 53
End Page Number: 68
Publication Date: Jun 1993
Journal: Mathematical Programming (Series A)
Authors:
Abstract:

The paper studies the max cut problem in graphs not contractible to K5, and optimum perfect matchings in planar graphs. It proves that both problems can be formulated as polynomial size linear programs.

Reviews

Required fields are marked *. Your email address will not be published.