A note on “A linear‐size zero‐one programming model for the minimum spanning tree problem in planar graphs”
A note on “A linear‐size zero‐one programming model for the minimum spanning tree problem in planar graphs”
复制标题
DOI：
10.1002/net.21849
复制
发表时间：
2018-10
期刊：
影响因子：
2.1
通讯作者：
Hamidreza Validi;Austin Buchanan
中科院分区：
文献类型：
--
作者：
Hamidreza Validi;Austin Buchanan
在文章“A linear‐size zero‐one programming model for the minimum spanning tree problem in planar graphs”（Networks 39（1）（2002），53‐60）中，威廉姆斯介绍了平面图的生成树多面体的扩展公式。这个公式非常小（只使用O（n）变量和约束），非常强（定义一个整数多面体）。在本说明中，我们指出，威廉姆斯的提法，如原来所说，是不正确的。具体来说，我们构造了一个二元可行的解决方案，威廉姆斯的制定，不代表一个生成树。幸运的是，有一个简单的解决办法，即限制原始和对偶生成树中根顶点的选择，而威廉姆斯明确允许它们任意选择。同样的缺陷和修复适用于威廉姆斯的后续公式（“一个零-一规划模型连续土地收购。”地理分析34（4）（2002），330 - 349）。
In the article “A linear‐size zero‐one programming model for the minimum spanning tree problem in planar graphs” (Networks 39(1) (2002), 53‐60), 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 zero‐one programming model for contiguous land acquisition.” Geographical Analysis 34(4) (2002), 330‐349).