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.
No takes yet. Share an insight, caveat, or question.
Eswaran et al. (1976) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: