## 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(λ^{2}n^{2}) time, where λ is the edge connectivity of G. Combining both algorithms yields an O(MIN{m, λ^{2}n}n) time algorithm for finding the edge connectivity of directed graphs. We also present an O(MIN{m, k^{2}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 | |

State | Published - Mar 1989 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics