Finding the edge connectivity of directed graphs

Yishay Mansour, Baruch Schieber

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

We present two algorithms for finding the edge connectivity of a given directed graph G. The first algorithm runs in O(nm) time, where n is the number of vertices and m is the number of edges in G. The second algorithm runs in O(λ2n2) time, where λ is the edge connectivity of G. Combining both algorithms yields an O(MIN{m, λ2n}n) time algorithm for finding the edge connectivity of directed graphs. We also present an O(MIN{m, k2n}n) time algorithm for deciding whether the edge connectivity of a given directed graph G is at least k. Both algorithms are superior to the best known algorithms for finding the edge connectivity of directed graphs.

Original languageEnglish (US)
Pages (from-to)76-85
Number of pages10
JournalJournal of Algorithms
Volume10
Issue number1
DOIs
StatePublished - Mar 1989
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Finding the edge connectivity of directed graphs'. Together they form a unique fingerprint.

Cite this