Arc-disjoint in-trees in directed graphs (Q987553): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
Created claim: Wikidata QID (P12): Q126592761, #quickstatements; #temporary_batch_1719314627150 |
||
Property / Wikidata QID | |||
Property / Wikidata QID: Q126592761 / rank | |||
Normal rank |
Latest revision as of 13:25, 25 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Arc-disjoint in-trees in directed graphs |
scientific article |
Statements
Arc-disjoint in-trees in directed graphs (English)
0 references
13 August 2010
0 references
The authors generalize an old theorem of \textit{J. Edmonds} [Combinatorial algorithms. R. Rustin eds. Courant computer science symposium 9: January 24--25, 1972 (1972; Zbl 0366.68023); pp. 91--96], and a result from \textit{A. Schrijver} [Algorithms and Combinatorics 24, Berlin, Springer (2003; Zbl 1041.90001)]. The first states that given a directed graph \(D=(V, A)\), with a specified vertex \(s \in V\), there exist \(k\) arc-disjoint in-trees rooted at \(s\) each of which spans \(V\) if and only if there are \(k\) arc-disjoint directed paths from any \(v \in V \setminus s\) and \(s\). In the other a vertex set \(S=\{s_1, \dots, s_d \}\) is specified together with a function \(f: S \rightarrow N\). A more or less straightforward generalization gives a necessary and sufficient condition for the existence of arc-disjoint in-trees \(T_{i, 1}, \dots, T_{i, f(s_i)}\), where \(T_{i, j}\) is rooted at \(s_i\), and each \(T_{i, j}\) spans \(V\). The main theorem of this paper generalizes this statement even more to the case where a \(T_{i, j}\) spans only a set \(V_i\), namely the set from which the vertex \(s_i\) is reachable.
0 references
arc-connectivity
0 references
directed trees
0 references
packing
0 references