Increasing the rooted connectivity of a digraph by one (Q1300061)

A two-phase greedy algorithm (when appropriately specialized) to find a minimum cost of new edges whose addition to a digraph increases the rooted connectivity by one is presented. The methods of \textit{D. F. Kornblum} [Proc. 9th southeast conf. on Combinatorics, graph theory and computing, Boca Raton 1978, 437-455 (1978; Zbl 0407.90089)] and \textit{D. R. Fulkerson} [Math. Program. 6, 1-13 (1974; Zbl 0283.05104)] are unified.