  


A Note on ``A linearsize zeroone programming model for the minimum spanning tree problem in planar graphs"
Hamidreza Validi (hamidreza.validiokstate.edu) Abstract: In the paper ``A linearsize zeroone programming model for the minimum spanning tree problem in planar graphs'' (Networks 39(1):5360, 2002), Williams introduced an extended formulation for the spanning tree polytope of a planar graph. This formulation is remarkably small (using only $O(n)$ variables and constraints) and remarkably strong (defining an integral polytope). In this note, we point out that Williams' formulation, as originally stated, is incorrect. Specifically, we construct a binary feasible solution to Williams' formulation that does not represent a spanning tree. Fortunately, there is a simple fix, which is to restrict the choice of the root vertices in the primal and dual spanning trees, whereas Williams explicitly allowed them to be chosen arbitrarily. The same flaw and fix apply to a subsequent formulation of Williams (``A ZeroOne Programming Model for Contiguous Land Acquisition.'' Geographical Analysis 34(4): 330349, 2002). Keywords: spanning tree; planar graph; planar dual; extended formulation; extension complexity; spanning arborescence; integer programming; Category 1: Integer Programming Category 2: Combinatorial Optimization Citation: Published in Networks: https://onlinelibrary.wiley.com/doi/full/10.1002/net.21849 Freely available at: https://docs.google.com/viewer?a=v&pid=sites&srcid=ZGVmYXVsdGRvbWFpbnxhdXN0aW5sYnVjaGFuYW58Z3g6M2U4YzBiZTY2NDVjMGYyYg Download: Entry Submitted: 07/04/2018 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  