Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.tcs.2010.04.019 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
efficient sequential algorithm,main algorithm,undirected graph,main issue,Partition constraint,resulting graph,bridge-connectivity augmentation problem,simple linear-time algorithm,partition constraint,simple graph,Bridge-connectivity,2-edge-connectivity,linear number,Augmentation,input graph,augmentation problem | Journal | 411 |
Issue | ISSN | Citations |
31-33 | Theoretical Computer Science | 4 |
PageRank | References | Authors |
0.46 | 17 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yen-Chiu Chen | 1 | 40 | 5.64 |
| Hsin-Wen Wei | 2 | 222 | 30.39 |
| Pei-Chi Huang | 3 | 64 | 9.92 |
| Wei-Kuan Shih | 4 | 938 | 98.21 |
| Tsan-sheng Hsu | 5 | 737 | 101.00 |