File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/978-3-662-48054-0
- Scopus: eid_2-s2.0-84944593186
- WOS: WOS:000371027300048
- Find via
Supplementary
- Citations:
- Appears in Collections:
Conference Paper: Efficient algorithm for computing all low s-t edge connectivities in directed graphs
Title | Efficient algorithm for computing all low s-t edge connectivities in directed graphs |
---|---|
Authors | |
Issue Date | 2015 |
Publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ |
Citation | The 40th International Symposium on Mathematical Foundations of Computer Science (MFCS 2015), Milano, Italy, 24-28 August 2015. In Lecture Notes in Computer Science, 2015, v. 9235, p. 577-588 How to Cite? |
Abstract | Given a directed graph with n nodes and m edges, the (strong) edge connectivity λ (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 ω) time by Cheung, Lau and Leung (FOCS 2011), where ω is the matrix multiplication factor (≈ 2:373), or in Õ (mn1: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 λ (u; v) ≤ 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 Õ (m+nk3), 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 ω, mn1:5)) when k ≤ √ n. Our algorithm also computes a minimum u-v cut for each pair of nodes (u; v) with λ (u; v) ≤ k. |
Description | LNCS v. 9235 entitled: Mathematical Foundations of Computer Science 2015: 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part 2 |
Persistent Identifier | http://hdl.handle.net/10722/219233 |
ISBN | |
ISSN | 2023 SCImago Journal Rankings: 0.606 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Wu, X | - |
dc.contributor.author | Zhang, C | - |
dc.date.accessioned | 2015-09-18T07:18:24Z | - |
dc.date.available | 2015-09-18T07:18:24Z | - |
dc.date.issued | 2015 | - |
dc.identifier.citation | The 40th International Symposium on Mathematical Foundations of Computer Science (MFCS 2015), Milano, Italy, 24-28 August 2015. In Lecture Notes in Computer Science, 2015, v. 9235, p. 577-588 | - |
dc.identifier.isbn | 978-366248053-3 | - |
dc.identifier.issn | 0302-9743 | - |
dc.identifier.uri | http://hdl.handle.net/10722/219233 | - |
dc.description | LNCS v. 9235 entitled: Mathematical Foundations of Computer Science 2015: 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part 2 | - |
dc.description.abstract | Given a directed graph with n nodes and m edges, the (strong) edge connectivity λ (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 ω) time by Cheung, Lau and Leung (FOCS 2011), where ω is the matrix multiplication factor (≈ 2:373), or in Õ (mn1: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 λ (u; v) ≤ 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 Õ (m+nk3), 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 ω, mn1:5)) when k ≤ √ n. Our algorithm also computes a minimum u-v cut for each pair of nodes (u; v) with λ (u; v) ≤ k. | - |
dc.language | eng | - |
dc.publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ | - |
dc.relation.ispartof | Lecture Notes in Computer Science | - |
dc.rights | The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-662-48054-0 | - |
dc.title | Efficient algorithm for computing all low s-t edge connectivities in directed graphs | - |
dc.type | Conference_Paper | - |
dc.description.nature | postprint | - |
dc.identifier.doi | 10.1007/978-3-662-48054-0 | - |
dc.identifier.scopus | eid_2-s2.0-84944593186 | - |
dc.identifier.hkuros | 254415 | - |
dc.identifier.volume | 9235 | - |
dc.identifier.spage | 577 | - |
dc.identifier.epage | 588 | - |
dc.identifier.isi | WOS:000371027300048 | - |
dc.publisher.place | Germany | - |
dc.customcontrol.immutable | sml 151229 | - |
dc.identifier.issnl | 0302-9743 | - |