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

孙雨耕; 吕 航; 郭培生; 吴 雪

您当前的位置：

首页 >

文章列表页 >

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

论文 | 更新时间：2025-07-16

- 有向树图的最小K点连通扩充
- The Augmentation Problem of a Directed Tree Graph to a K-Connected Graph
- 电子学报 2004年32卷第2期页码：200-204
- 作者机构：
  
  天津大学电气与自动化工程学院,天津,300072
- 作者简介：
- 基金信息：
  
  教育部博士学科点基金 (No.20030056007)
- DOI：
  中图分类号： TN915
- 纸质出版：2004
- 稿件说明：
移动端阅览
孙雨耕, 吕航, 郭培生, 等. 有向树图的最小K点连通扩充[J]. 电子学报, 2004,32(2):200-204.

SUN Yu-geng, LV Hang, GUO Pei-sheng, et al. The Augmentation Problem of a Directed Tree Graph to a K-Connected Graph[J]. Acta Electronica Sinica, 2004, 32(2): 200-204.
孙雨耕, 吕航, 郭培生, 等. 有向树图的最小K点连通扩充[J]. 电子学报, 2004,32(2):200-204. DOI：

SUN Yu-geng, LV Hang, GUO Pei-sheng, et al. The Augmentation Problem of a Directed Tree Graph to a K-Connected Graph[J]. Acta Electronica Sinica, 2004, 32(2): 200-204. DOI：

摘要

本文解决了图论的连通性理论中的一个重要的问题——以最小边集扩充一个任意有向树图为

点连通图

证明了该问题在算法上属于

问题

提出了一个时间复杂度为

O(|V|

)

的有效算法DTKA

该算法为可靠通讯网的计算机辅助设计提供了一个基础.

Abstract

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.

关键词

Keywords

references

浏览量

916

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据