Skip to Main content Skip to Navigation
Conference papers

Packing non-returning A-paths algorithmically

Abstract : 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.
Keywords : A-paths matching
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Friday, August 14, 2015 - 11:37:05 AM
Last modification on : Thursday, May 11, 2017 - 1:03:05 AM
Long-term archiving on: : Sunday, November 15, 2015 - 10:58:55 AM


Publisher files allowed on an open archive




Gyula Pap. Packing non-returning A-paths algorithmically. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.139-144, ⟨10.46298/dmtcs.3399⟩. ⟨hal-01184355⟩



Record views


Files downloads