Packing non-zero \(A\)-paths in group-labelled graphs (Q879161): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s00493-006-0030-1 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2159330890 / rank | |||
Normal rank |
Latest revision as of 00:22, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Packing non-zero \(A\)-paths in group-labelled graphs |
scientific article |
Statements
Packing non-zero \(A\)-paths in group-labelled graphs (English)
0 references
8 May 2007
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\). (If \(\Gamma\) is not abelian, we sum the labels in their order along the path.) The authors give a connection of this problem to some other problems studied in the literature. The authors prove that for any integer \(k\), either there are \(k\)-vertex-disjoint \(A\)-paths each of non-zero weight, or there is a set of at most \(2k-2\) vertices that meets each non-zero \(A\)-path.
0 references
packing non-zero paths
0 references
group-labelled graphs
0 references