An algorithm for packing non-zero A-paths in group-labelled graphs |
| |
Authors: | Maria Chudnovsky William H Cunningham Jim Geelen |
| |
Institution: | (1) Department of Industrial Engineering and Operations Research, Columbia University, New York, NY 10027, USA;(2) Department of Combinatorics and Optimization, University of Waterloo, Waterloo, N2L 3G1, Canada |
| |
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.
This research was partially conducted during the period Chudnovsky served as a Clay Mathematics Institute Long-Term Prize
Fellow. The research was supported in part by the Natural Sciences and Engineering Council of Canada. |
| |
Keywords: | 05C22 |
本文献已被 SpringerLink 等数据库收录! |
|