### Abstract

Let G = (V, E) be an oriented graph whose edges are labelled by the elements of a group Γ and let A ⊆ V. An A-path is a path whose ends are both in A. The weight of a path P in G is the sum of the group values on forward oriented arcs minus the sum of the backward oriented arcs in P. (If Γ is not abelian, we sum the labels in their order along the path.) We give an efficient algorithm for finding a maximum collection of vertex-disjoint A-paths each of non-zero weight. When A = V this problem is equivalent to the maximum matching problem.

Original language | English (US) |
---|---|

Pages (from-to) | 145-161 |

Number of pages | 17 |

Journal | Combinatorica |

Volume | 28 |

Issue number | 2 |

DOIs | |

State | Published - Mar 1 2008 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics
- Computational Mathematics

## Fingerprint Dive into the research topics of 'An algorithm for packing non-zero a-paths in group-labelled graphs'. Together they form a unique fingerprint.

## Cite this

Chudnovsky, M., Cunningham, W. H., & Geelen, J. (2008). An algorithm for packing non-zero a-paths in group-labelled graphs.

*Combinatorica*,*28*(2), 145-161. https://doi.org/10.1007/s00493-008-2157-8