Increasing the rooted-connectivity of a digraph by one

D.R. Fulkerson described a two-phase greedy algorithm to find a minimum cost spanning arborescence and to solve the dual linear program. This was extended by the present author for ‚kernel systems’, a model including the rooted edge-connectivity augumentation problem, as well. A similar type of method was developed by D. Kornblum for ‚lattice polyhedra’, a notion introduced by A. Hoffman and D.E. Schwartz. In order to unify these approaches, here we describe a two-phase greedy algorithm working on a slight extension of lattice polyhedra. This framework includes the rooted node-connectivity augmentation problem, as well, and hence the resulting algorithm, when appropriately specialized, finds a minimum cost of new edges whose addition to a digraph increases its rooted connectivity by one. The only known algorithm for this problem used submodular flows. Actually, the specialized algorithm solves an extension of the rooted edge-connectivity and node-connectivity augmentation problem.