| The Bridge-connectivity Augmentation Problem with a partition Constraint | |
|---|---|
| 學年 | 98 |
| 學期 | 2 |
| 出版（發表）日期 | 2010-06-01 |
| 作品名稱 | The Bridge-connectivity Augmentation Problem with a partition Constraint |
| 作品名稱（其他語言） | |
| 著者 | Chen, Yen-Chiu; Wei, Hsin-Wen; Huang, Pei-Chi; Shih, Wei-Kuan; Hsu, Tsan-sheng |
| 單位 | 淡江大學電機工程學系 |
| 出版者 | Amsterdam: Elsevier BV |
| 著錄名稱、卷期、頁數 | Theoretical Computer Science 411(31–33), pp.2878–2889 |
| 摘要 | 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. |
| 關鍵字 | 2-edge-connectivity; Bridge-connectivity; Augmentation; Partition constraint |
| 語言 | en |
| ISSN | 0304-3975 |
| 期刊性質 | 國外 |
| 收錄於 | SCI |
| 產學合作 | |
| 通訊作者 | Wei, Hsin-Wen |
| 審稿制度 | |
| 國別 | NLD |
| 公開徵稿 | Y |
| 出版型式 | 紙本 |
| 相關連結 |
機構典藏連結 ( http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/96126 ) |
GoogleAnalytics