Total Dual Integrality of Matching Forest Constraints
Total Dual Integrality of Matching Forest Constraints
复制标题
匹配森林约束的总对偶完整性
DOI：
10.1007/s004930070009
复制
发表时间：
2000
期刊：
影响因子：
1.1
通讯作者：
A. Schrijver
中科院分区：
文献类型：
--
作者：
A. Schrijver
（V， E， A）是混合图。也就是说，（V， E）是一个无向图（V， A）是一个有向图。匹配森林（由R. Giles引入）是这样一个子集F，即F不包含电路（在底层无向图中），并且对于每个电路，最多有一个使得v是e的头（对于无向边e， e的两端都称为e的头）。Giles给出了一种多项式时间算法来寻找最大权值匹配森林，作为副产品产生了决定匹配森林的关联向量凸包的不等式的表征。我们证明了这些不等式构成了一个完全对偶积分系统。它相当于匹配森林的最大权重的“全整数”最小-最大关系。我们的证明是基于匹配森林的交换性质，并隐含了Giles的表征。
G=(V, E, A) be a mixed graph. That is, (V, E) is an undirected graph and (V, A) is a directed graph. A matching forest (introduced by R. Giles) is a subset F of such that F contains no circuit (in the underlying undirected graph) and such that for each there is at most one such that v is head of e. (For an undirected edge e, both ends of e are called head of e.) Giles gave a polynomial-time algorithm to find a maximum-weight matching forest, yielding as a by-product a characterization of the inequalities determining the convex hull of the incidence vectors of the matching forests. We prove that these inequalities form a totally dual integral system. It is equivalent to an ``all-integer'' min-max relation for the maximum weight of a matching forest. Our proof is based on an exchange property for matching forests, and implies Giles' characterization.