APPROXIMATION ALGORITHMS FOR SEVERAL GRAPH AUGMENTATION PROBLEMS

作     者：FREDERICKSON, GN JAJA, J 

出 版 物：《SIAM JOURNAL ON COMPUTING》 

年 卷 期：1981年第10卷第2期

页      面：270-283页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：approximation algorithm augmentation biconnectivity bridge-connectivity connectivity graph NP-complete problem strong connectivity 

摘      要：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.