Premium
A linear‐size zero—one programming model for the minimum spanning tree problem in planar graphs
Author(s) -
Williams Justin C.
Publication year - 2002
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10010
Subject(s) - unimodular matrix , linear programming , integer programming , mathematics , combinatorics , steiner tree problem , spanning tree , planar graph , minimum spanning tree , generalization , mathematical optimization , graph , discrete mathematics , mathematical analysis
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. © 2001 John Wiley & Sons, Inc.