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

SUN Yu-geng; LV Hang; GUO Pei-sheng; WU Xue

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2025-07-16

- The Augmentation Problem of a Directed Tree Graph to a K-Connected Graph
- Acta Electronica Sinica Vol. 32, Issue 2, Pages: 200-204(2004)
- 作者机构：
  
  天津大学电气与自动化工程学院,天津,300072
- 作者简介：
- 基金信息：
- DOI：
  CLC： TN915
- Published：2004
- 稿件说明：
移动端阅览
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：

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

Views

916

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

⁰