Name
Abstract | ||
|---|---|---|
We consider the distributed construction of a minimum weight 2- edge-connected spanning subgraph (2-ECSS) of a given weighted or unweighted graph. A 2-ECSS of a graph is a subgraph that, for each pair of vertices, contains at least two edge-disjoint paths connecting these vertices. The problem of finding a minimum weight 2-ECSS is NP-hard and a natural extension of the distributed MST construction problem, one of the most fundamental problems in the area of distributed computation. We present a distributed 3/2-approximation algorithm for the unweighted 2-ECSS construction problem that requires O(n) communication rounds and O(m) messages. Moreover, we present a distributed 3-approximation algorithm for the weighted 2-ECSS construction problem that requires O(nlogn) communication rounds and O(nlog2 n+m) messages. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-77096-1_12 | OPODIS |
Keywords | Field | DocType |
2-edge-connected subgraphs,minimum weight 2-ecss,mst construction problem,3-approximation algorithm,communication round,minimum weight,2-approximation algorithm,unweighted graph,fundamental problem,2-ecss construction problem,edge-disjoint path,distributed computing | Discrete mathematics,Graph,Approximation algorithm,Spanning subgraph,Distributed minimum spanning tree,Vertex (geometry),Computer science,Theoretical computer science,Minimum weight,Computation,Distributed computing | Conference |
Volume | ISSN | ISBN |
4878 | 0302-9743 | 3-540-77095-X |
Citations | PageRank | References |
2 | 0.38 | 14 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sven O. Krumke | 1 | 308 | 36.62 |
| Peter Merz | 2 | 329 | 20.71 |
| Tim Nonner | 3 | 61 | 6.11 |
| Katharina Rupp | 4 | 2 | 0.38 |