The minimum augmentation of a directed tree to a k‐edge‐connected directed graph
Authors:
Abstract
For a directed graph G, let d+(ν) and d (ν) be the outdegree and indegree of vertex ν, respectively. Given a positive integer k, the outdeficiency and indeficiency are defined by δ (ν) = max (k − d+ (ν), 0) and δ (ν) = max(k − d− (ν), 0), respectively. It is evident that in augmenting G to a k‐edge‐connected directed graph, at least δk(G) = max(Σδ (ν), Σδ (ν)) edges are necessary. This paper proves the theorem that if G is a directed tree (directed graph whose underlying graph is a tree) this number of edges is enough. The proof is made by presenting a construction procedure of polynomial‐order complexity.Keywords
This publication has 1 reference indexed in Scilit:
- Augmentation ProblemsSIAM Journal on Computing, 1976