A linear-size zero–one programming model for the minimum spanning tree problem in planar graphs

A linear-size zero–one programming model for the minimum spanning tree problem in planar graphs

0.00 Avg rating0 Votes
Article ID: iaor20031160
Country: United States
Volume: 39
Issue: 1
Start Page Number: 53
End Page Number: 60
Publication Date: Jan 2002
Journal: Networks
Authors:
Keywords: programming: integer, programming: network
Abstract:

A new linear zero–one programming model is presented for the problem of finding minimum spanning trees (MSTs) in undirected planar graphs. Existing MST solution algorithms, which are applicable to both planar and nonplanar graphs, have strong computational advantages over existing MST integer–linear programming (LP) models. The latter tend not to be amenable to LP solution methods except for relatively small problems, but may, nevertheless, be desirable for reasons of convenience, exibility, and adaptability to related and difficult problems such as the network Steiner tree problem. The purpose of this paper was to present a zero–one model whose size and solvability more closely resemble the properties of existing algorithms than do other proposed integer–LP models. This new model exploits the special primal–dual structure that exists for planar graphs. The model's constraint matrix is both unimodular and linear in size relative to graph size. Hence, LP solution methods become practical for solving large planar graph MST problems exactly. A bi-objective generalization of the model is presented and the model's LP dual is briefly discussed.

Reviews

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