教師資料查詢 | 類別: 期刊論文 | 教師: 衛信文 Wei, Hsin-Wen (瀏覽個人網頁)

標題:Smallest Bipartite Bridge-connectivity Augmentation
學年97
學期2
出版(發表)日期2009/07/01
作品名稱Smallest Bipartite Bridge-connectivity Augmentation
作品名稱(其他語言)
著者Huang, Pei-Chi; Wei, Hsin-Wen; Lu, Wan-Chen; Shih, Wei-Kuan; Hsu, Tsan-sheng
單位淡江大學電機工程學系
出版者New York: Springer New York LLC
著錄名稱、卷期、頁數Algorithmica 54(3), pp.353-378
摘要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.
關鍵字2-edge-connectivity; Bridge-connectivity; Data security; Bipartite graph augmentation
語言英文(美國)
ISSN0178-4617;1432-0541
期刊性質國外
收錄於SCI
產學合作
通訊作者Wei, Hsin-Wen
審稿制度
國別美國
公開徵稿Y
出版型式紙本;電子版
相關連結
Google+ 推薦功能,讓全世界都能看到您的推薦!