Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
Citations Over TimeTop 10% of 1992 papers
Abstract
Given an undirected graph $G = ( V,E )$, it is known that its edge-connectivity $\lambda ( G )$ can be computed by solving $O( | V | )$ max-flow problems. The best time bounds known for the problem are $O( \lambda ( G ) | V |^2 )$, due to Matula (28th IEEE Symposium on the Foundations of Computer Science, 1987, pp. 249–251) if G is simple, and $O( | E |^{3/2} | V | )$, due to Even and Tarjan (SIAM J. Comput., 4 (1975), pp. 507–518) if G is multiple. An $O( | E | + \min \{ \lambda ( G ) | V |^2 ,p | V | + | V |^2 \log | V | \} )$ time algorithm for computing the edge-connectivity $\lambda ( G )$ of a multigraph $G = ( V,E )$, where $p ( \leqq | E | )$ is the number of pairs of nodes between which G has an edge, is proposed. This algorithm does not use any max-flow algorithm but consists only of $| V |$ times of graph searches and edge contractions. This method is then extended to a capacitated network to compute its minimum cut capacity in $O ( | V | | E | + | V |^2 \log | V | )$ time.
Related Papers
- → A Faster Algorithm for Finding the Minimum Cut in a Directed Graph(1994)224 cited
- A faster algorithm for finding the minimum cut in a graph(1992)
- → Polynomial flow-cut gaps and hardness of directed cut problems(2007)17 cited
- Selected applications of maximum flows and minimum cuts in networks(1979)