Graph augmentation problems on a weighted graph involve determining a minimum-cost set of edges to add to a graph to satisfy a specified property, such as biconnectivity, bridge-connectivity or strong connectivity. These augmentation problems are shown to be NP-complete in the restricted case of the graph being initially connected. Approximation algorithms with favorable time complexity are presented and shown to have constant worst-case performance ratios.
No takes yet. Share an insight, caveat, or question.
Frederickson et al. (1981) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: