TR-2005-12

Packing non-returning A-paths

Gyula Pap



Abstract

Chudnovsky et al. gave a min-max formula for the maximum number of node-disjoint non-zero 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 \widehat{\nu}, which is given by an oracle for non-bipartite matching.


Bibtex entry:

@techreport{egres-05-12,
AUTHOR = {Pap, Gyula},
TITLE = {Packing non-returning $A$-paths},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2005},
NUMBER = {TR-2005-12}
}


Last modification: 5.6.2018. Please email your comments to Tamás Király!