Arc-disjoint in-trees in directed graphs
type: Item
instance of: scholarly article
title: Arc-disjoint in-trees in directed graphs
zbMATH Open document ID: 1212.05209
author: Naoyuki Kamiyama
author: Naoki Katoh
author: Atsushi Takizawa
published in: Combinatorica
publication date: 2010-08-13T00:00:00Z
full work available at URL: http://hdl.handle.net/2433/123379
review text: 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.
reviewed by: András Pluhár
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 5770358
zbMATH Keywords: arc-connectivity
zbMATH Keywords: directed trees
zbMATH Keywords: packing
MaRDI profile type: Publication
OpenAlex ID: W1987229183
Wikidata QID: Q126592761
DOI: 10.1007/S00493-009-2428-Z
description: scientific article; zbMATH DE number 5770358