Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Fast Computation of Small Cuts via Cycle Space Sampling
 
research article

Fast Computation of Small Cuts via Cycle Space Sampling

Pritchard, David  
•
Thurimella, Ramakrishna
2011
Acm Transactions On Algorithms

We describe a new sampling-based method to determine cuts in an undirected graph. For a graph (V, E), its cycle space is the family of all subsets of E that have even degree at each vertex. We prove that with high probability, sampling the cycle space identifies the cuts of a graph. This leads to simple new linear-time sequential algorithms for finding all cut edges and cut pairs (a set of 2 edges that form a cut) of a graph. In the model of distributed computing in a graph G=(V, E) with O(log V)-bit messages, our approach yields faster algorithms for several problems. The diameter of G is denoted by Diam, and the maximum degree by Delta. We obtain simple O(Diam)-time distributed algorithms to find all cut edges, 2-edge-connected components, and cut pairs, matching or improving upon previous time bounds. Under natural conditions these new algorithms are universally optimal --- i.e. a Omega(Diam)-time lower bound holds on every graph. We obtain a O(Diam+Delta/log V)-time distributed algorithm for finding cut vertices; this is faster than the best previous algorithm when Delta, Diam = O(sqrt(V)). A simple extension of our work yields the first distributed algorithm with sub-linear time for 3-edge-connected components. The basic distributed algorithms are Monte Carlo, but they can be made Las Vegas without increasing the asymptotic complexity. In the model of parallel computing on the EREW PRAM our approach yields a simple algorithm with optimal time complexity O(log V) for finding cut pairs and 3-edge-connected components.

  • Details
  • Metrics
Type
research article
DOI
10.1145/2000807.2000814
ArXiv ID

cs/0702113

Author(s)
Pritchard, David  
Thurimella, Ramakrishna
Date Issued

2011

Published in
Acm Transactions On Algorithms
Volume

7

Issue

54

Start page

46

Subjects

Distributed algorithms

•

graph connectivity

•

linear algebra

•

parallel algorithms

•

randomized algorithms

•

universal optimality

•

Biconnected Components

•

Distributed Algorithm

•

Erew Pram

•

Efficient

•

Graphs

•

Networks

Note

Preliminary version appeared in Proc. 35th ICALP, 2008.

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DISOPT  
Available on Infoscience
August 24, 2010
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/52379
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés