Gyula Pap
-
Packing non-returning A-paths algorithmically
dmtcs:3399 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2005,
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
-
https://doi.org/10.46298/dmtcs.3399
Packing non-returning A-paths algorithmicallyConference paper
Authors: Gyula Pap 1
NULL
Gyula Pap
1 Operations Research Department
In this paper we present an algorithmic approach to packing A-paths. It is regarded as a generalization of Edmonds' matching algorithm, however there is the significant difference that here we do not build up any kind of alternating tree. Instead we use the so-called 3-way lemma, which either provides augmentation, or a dual, or a subgraph which can be used for contraction. The method works in the general setting of packing non-returning A-paths. It also implies an ear-decomposition of criticals, as a generalization of the odd ear-decomposition of factor-critical graph.
Yoichi Iwata;Magnus Wahlström;Yuichi Yoshida, 2016, Half-integrality, LP-branching, and FPT Algorithms, arXiv (Cornell University), 45, 4, pp. 1377-1411, 10.1137/140962838, https://arxiv.org/abs/1310.2841.
Yutaro Yamaguchi, 2016, Packing A-Paths in Group-Labelled Graphs via Linear Matroid Parity, SIAM Journal on Discrete Mathematics, 30, 1, pp. 474-492, 10.1137/130949877.