有向树图的最小K点连通扩充  

The Augmentation Problem of a Directed Tree Graph to a K-Connected Graph

作　　者：孙雨耕[1] 吕航[1] 郭培生[1] 吴雪[1] 

机构地区：[1]天津大学电气与自动化工程学院,天津300072

出　　处：《电子学报》2004年第2期200-204,共5页Acta Electronica Sinica

基　　金：教育部博士学科点基金 (No.2 0 0 30 0 560 0 7)

摘　　要：本文解决了图论的连通性理论中的一个重要的问题———以最小边集扩充一个任意有向树图为K点连通图 ,证明了该问题在算法上属于P问题 ,提出了一个时间复杂度为O(|V|3 )的有效算法DTKA 。This paper studies an important problem in Connectivity Theory--augmenting a directed tree graph to a K Vertex Connected graph by adding a minimum set of edges and proves that this problem is P Problem.An effective algorithm DTKA with complexity of is given.This algorithm contributes a foundation to the Computer Aided Design of reliable communication networks.

关 键 词：有向树图 最小扩充 K点连通 

分 类 号：TN915[电子电信—通信与信息系统]