Finding the edge connectivity of directed graphs

Yishay Mansour; Baruch Schieber

doi:10.1016/0196-6774(89)90024-2

Finding the edge connectivity of directed graphs

Yishay Mansour, Baruch Schieber

Research output: Contribution to journal › Article › peer-review

9 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(λ²n²) time, where λ is the edge connectivity of G. Combining both algorithms yields an O(MIN{m, λ²n}n) time algorithm for finding the edge connectivity of directed graphs. We also present an O(MIN{m, k²n}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 language	English (US)
Pages (from-to)	76-85
Number of pages	10
Journal	Journal of Algorithms
Volume	10
Issue number	1
DOIs	https://doi.org/10.1016/0196-6774(89)90024-2
State	Published - Mar 1989
Externally published	Yes

All Science Journal Classification (ASJC) codes

Control and Optimization
Computational Mathematics
Computational Theory and Mathematics

Access to Document

10.1016/0196-6774(89)90024-2

Cite this

@article{c15f80a703d5465abf62d0130d3f6fec,

title = "Finding the edge connectivity of directed graphs",

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.",

author = "Yishay Mansour and Baruch Schieber",

note = "Funding Information: *Supported by an ISEF fellowship and by NSF Contract CCR8611442.",

year = "1989",

month = mar,

doi = "10.1016/0196-6774(89)90024-2",

language = "English (US)",

volume = "10",

pages = "76--85",

journal = "Journal of Algorithms",

issn = "0196-6774",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - Finding the edge connectivity of directed graphs

AU - Mansour, Yishay

AU - Schieber, Baruch

N1 - Funding Information: *Supported by an ISEF fellowship and by NSF Contract CCR8611442.

PY - 1989/3

Y1 - 1989/3

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/38249024788

UR - https://www.scopus.com/inward/citedby.url?scp=38249024788&partnerID=8YFLogxK

U2 - 10.1016/0196-6774(89)90024-2

DO - 10.1016/0196-6774(89)90024-2

M3 - Article

AN - SCOPUS:38249024788

SN - 0196-6774

VL - 10

SP - 76

EP - 85

JO - Journal of Algorithms

JF - Journal of Algorithms

IS - 1

ER -

Finding the edge connectivity of directed graphs

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this