A fast algorithm for computing Steiner edge connectivity

Richard Cole, Ramesh Hariharan

Research output: Contribution to journalConference articlepeer-review

Abstract

Given an undirected graph or an Eulerian directed graph G and a subset S of its vertices, we show how to determine the edge connectivity C of the vertices in S in time O(C3n logn + m). This algorithm is based on an efficient construction of tree packings which generalizes Edmonds' Theorem. These packings also yield a characterization of all minimal Steiner cuts of size C from which an efficient data structure for maintaining edge connectivity between vertices in S under edge insertion can be obtained. This data structure enables the efficient construction of a cactus tree for representing significant C-cuts among these vertices, called C-separations, in the same time bound. In turn, we use the cactus tree to give a fast implementation of an approximation algorithm for the Survivable Network Design problem due to Williamson, Goemans, Mihail and Vazirani.

Original languageEnglish (US)
Pages (from-to)167-176
Number of pages10
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - 2003
Event35th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States
Duration: Jun 9 2003Jun 11 2003

Keywords

  • Cactus trees
  • Edge-connectivity
  • Steiner points

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'A fast algorithm for computing Steiner edge connectivity'. Together they form a unique fingerprint.

Cite this