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

https://hal.inria.fr/hal-01184355
Contributor : Coordination Episciences Iam <>
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

File

dmAE0128.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184355, version 1

Collections

Citation

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. ⟨hal-01184355⟩

Share

Metrics

Record views

148

Files downloads

978