Lecture Notes in Computer Science, 2007, Volume 4878/2007, 159-173, DOI: 10.1007/978-3-540-77096-1_12

Distributed Approximation Algorithms for Finding 2-Edge-Connected Subgraphs

Sven O. Krumke, Peter Merz, Tim Nonner and Katharina Rupp

View Related Documents

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 \frac32 \frac{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( n logn ) communication rounds and O( n log2 n + m ) messages.

Fulltext Preview

Image of the first page of the fulltext document