Smallest Bipartite Bridge-connectivity Augmentation

doi:10.1007/s00453-007-9127-1

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

請使用永久網址來引用或連結此文件: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/96127

題名:	Smallest Bipartite Bridge-connectivity Augmentation
作者:	Huang, Pei-Chi;Wei, Hsin-Wen;Lu, Wan-Chen;Shih, Wei-Kuan;Hsu, Tsan-sheng
貢獻者:	淡江大學電機工程學系
關鍵詞:	2-edge-connectivity;Bridge-connectivity;Data security;Bipartite graph augmentation
日期:	2009-07
上傳時間:	2014-03-03 16:27:08 (UTC+8)
出版者:	New York: Springer New York LLC
摘要:	This paper addresses two augmentation problems related to bipartite graphs. The first, a fundamental graph-theoretical problem, 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, and still bipartite. The second problem, which arises naturally from research on the security of statistical data, is how to add edges so that the resulting graph is simple and does not contain any bridges. In both cases, after adding edges, the graph can be either a simple graph or, if necessary, a multi-graph. Our approach then determines whether or not such an augmentation is possible. We propose a number of simple linear-time algorithms to solve both problems. Given the well-known bridge-block data structure for an input graph, the algorithms run in O(log n) parallel time on an EREW PRAM using a linear number of processors, where n is the number of vertices in the input graph. We note that there is already a polynomial time algorithm that solves the first augmentation problem related to graphs with a given general partition constraint in O(n(m+nlog n)log n) time, where m is the number of distinct edges in the input graph. We are unaware of any results for the second problem.
關聯:	Algorithmica 54(3), pp.353-378
DOI:	10.1007/s00453-007-9127-1
顯示於類別:	[電機工程學系暨研究所] 期刊論文

文件中的檔案:

檔案	描述	大小	格式	瀏覽次數
index.html		0Kb	HTML	247	檢視/開啟

在機構典藏中所有的資料項目都受到原著作權保護.

TAIR相關文章

資料載入中.....