1976/12/01 by Kapali P. Eswaran, Robert E. Tarjan, R. Endre Tarjan · 7 citations
Computer Science · #Interconnection Networks and Systems #Optimization and Search Problems #Graph Theory and Algorithms
paper · doi:10.1137/0205044
This paper considers problems in which the object is to add a minimum-weight set of edges to a graph so as to satisfy a given connectivity condition. Simple characterizations of the minimum number of edges necessary to make a directed graph strongly connected and to make an undirected graph bridge-connected or biconnected are given. Efficient algorithms for finding such minimum sets of edges are discussed. It is shown that the weighted versions of these problems are NP-complete.