On Polyhedra Related to Even Factors
On Polyhedra Related to Even Factors
复制标题
关于偶数因子的多面体
DOI：
10.1007/978-3-540-25960-2_31
复制
发表时间：
2004
影响因子：
0.9
通讯作者：
M. Makai
中科院分区：
文献类型：
--
作者：
Tamás Király;M. Makai
作为匹配和拟阵交的一种常见推广，W.H.坎宁安和J.F.杰伦引入了路径匹配的概念，他们通过引入弱对称有向图的偶因子进一步对其进行了推广。后来，Gy.帕普和L.塞格给出了一种研究偶因子的纯组合方法，他们表明在几乎对称有向图类中，最大偶因子问题仍然是可处理的。本文展示了一种直接的多面体方法来推导加权整数最小 - 最大公式，对之前的那些结果进行了推广。
As a common generalization of matchings and matroid intersection, W.H. Cunningham and J.F. Geelen introduced the notion of path-matching, which they generalized even further by introducing even factors of weakly symmetric digraphs. Later, a purely combinatorial approach to even factors was given by Gy. Pap and L. Szegő, who showed that the maximum even factor problem remains tractable in the class of hardly symmetric digraphs. The present paper shows a direct polyhedral way to derive weighted integer min-max formulae generalizing those previous results.