Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Efficient Algorithm for Computing All Low s-t Edge Connectivities in Directed Graphs
verfasst von : Xiaowei Wu, Chenzi Zhang
Erschienen in: Mathematical Foundations of Computer Science 2015
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Given a directed graph with n nodes and m edges, the (strong) edge connectivity \(\lambda (u,v)\) between two nodes u and v is the minimum number of edges whose deletion makes u and v not strongly connected. The problem of computing the edge connectivities between all pairs of nodes of a directed graph can be done in \(O(m^\omega )\) time by Cheung, Lau and Leung (FOCS 2011), where \(\omega \) is the matrix multiplication factor (\(\approx 2.373\)), or in \(\tilde{O}(mn^{1.5})\) time using O(n) computations of max-flows by Cheng and Hu (IPCO 1990).
We consider in this paper the “low edge connectivity” problem, which aims at computing the edge connectivities for the pairs of nodes (u, v) such that \(\lambda (u,v)\le k\). While the undirected version of this problem was considered by Hariharan, Kavitha and Panigrahi (SODA 2007), who presented an algorithm with expected running time \(\tilde{O}(m+nk^3)\), no algorithm better than computing all-pairs edge connectivities was proposed for directed graphs. We provide an algorithm that computes all low edge connectivities in O(kmn) time, improving the previous best result of \(O(\min (m^\omega , mn^{1.5}))\) when \(k\le \sqrt{n}\). Our algorithm also computes a minimum u-v cut for each pair of nodes (u, v) with \(\lambda (u,v)\le k\).