Packing Non-Returning A-Paths* |
| |
Authors: | Gyula Pap† |
| |
Affiliation: | 1.Dept. of Operations Research,E?tv?s University,Budapest,Hungary |
| |
Abstract: | Chudnovsky et al. gave a min-max formula for the maximum number of node-disjoint nonzero A-paths in group-labeled graphs [1], which is a generalization of Mader's theorem on node-disjoint A-paths [3]. Here we present a further generalization with a shorter proof. The main feature of Theorem 2.1 is that parity is “hidden” inside , which is given by an oracle for non-bipartite matching. * Research is supported by OTKA grants T 037547 and TS 049788, by European MCRTN Adonet, Contract Grant No. 504438 and by the Egerváry Research Group of the Hungarian Academy of Sciences. † The author is a member of the Egerváry Research Group (EGRES). |
| |
Keywords: | 05C70 05C40 |
本文献已被 SpringerLink 等数据库收录! |
|