An algorithm for packing non-zero \(A\)-paths in group-labelled graphs (Q949790): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Packing non-zero \(A\)-paths in group-labelled graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Matroid matching and some applications / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Über die Maximalzahl kreuzungsfreier H-Wege / rank | |||
Normal rank |
Latest revision as of 18:47, 28 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An algorithm for packing non-zero \(A\)-paths in group-labelled graphs |
scientific article |
Statements
An algorithm for packing non-zero \(A\)-paths in group-labelled graphs (English)
0 references
21 October 2008
0 references
Let \(G=(V,E)\) be an oriented graph whose edges are labelled by the elements of a group \(\Gamma\) and let \(A\subseteq 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\). An efficient algorithm is given 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.
0 references
oriented graph
0 references
\(A\)-path
0 references
weight of a path
0 references