Approximation Algorithms for Several Graph Augmentation Problems

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...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on computing 1981-05, Vol.10 (2), p.270-283
Main Authors: Frederickson, Greg N., Ja’Ja’, Joseph
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Computer science
Connectivity
Graphs
Leaves
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0097-5397
1095-7111
DOI:10.1137/0210019