An algorithm for packing non-zero \(A\)-paths in group-labelled graphs (Q949790): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s00493-008-2157-8 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2032198109 / rank | |||
Normal rank | |||
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 | |||
links / mardi / name | links / mardi / name | ||
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