The Bridge-connectivity Augmentation Problem with a partition Constraint

淡江大學機構典藏 > 工學院 > 電機工程學系暨研究所 > 期刊論文 > Item 987654321/96126

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/96126

题名:	The Bridge-connectivity Augmentation Problem with a partition Constraint
作者:	Chen, Yen-Chiu;Wei, Hsin-Wen;Huang, Pei-Chi;Shih, Wei-Kuan;Hsu, Tsan-sheng
贡献者:	淡江大學電機工程學系
关键词:	2-edge-connectivity;Bridge-connectivity;Augmentation;Partition constraint
日期:	2010-06
上传时间:	2014-03-03 16:19:35 (UTC+8)
出版者:	Amsterdam: Elsevier BV
摘要:	In this paper, we consider the augmentation problem of an undirected graph with k partitions of its vertices. The main issue is how to add a set of edges with the smallest possible cardinality so that the resulting graph is 2-edge-connected, i.e., bridge-connected, while maintaining the original partition constraint. To solve the problem, we propose a simple linear-time algorithm. To the best of our knowledge, the most efficient sequential algorithm runs in O(n(m+nlogn)logn) time. However, we show that it can also run in O(logn) parallel time on an EREW PRAM using a linear number of processors, where n is the number of vertices in the input graph. If a simple graph exists, our main algorithm ensures that it is as simple as possible.
關聯:	Theoretical Computer Science 411(31–33), pp.2878–2889
DOI:	10.1016/j.tcs.2010.04.019
显示于类别:	[電機工程學系暨研究所] 期刊論文

文件中的档案:

档案	描述	大小	格式	浏览次数
index.html		0Kb	HTML	270	检视/开启

在機構典藏中所有的数据项都受到原著作权保护.

TAIR相关文章