File Download
Links for fulltext
(May Require Subscription)
 Publisher Website: 10.1007/9783662480540
 Scopus: eid_2s2.084944593186
 Find via
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Conference Paper: Efficient algorithm for computing all low st edge connectivities in directed graphs
Title  Efficient algorithm for computing all low st 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, 2428 August 2015. In Lecture Notes in Computer Science, 2015, v. 9235, p. 577588 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 maxflows 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 allpairs 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 uv 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 2428, 2015, Proceedings, Part 2 
Persistent Identifier  http://hdl.handle.net/10722/219233 
ISBN  
ISSN  2005 Impact Factor: 0.302 2015 SCImago Journal Rankings: 0.252 
DC Field  Value  Language 

dc.contributor.author  Wu, X   
dc.contributor.author  Zhang, C   
dc.date.accessioned  20150918T07:18:24Z   
dc.date.available  20150918T07:18:24Z   
dc.date.issued  2015   
dc.identifier.citation  The 40th International Symposium on Mathematical Foundations of Computer Science (MFCS 2015), Milano, Italy, 2428 August 2015. In Lecture Notes in Computer Science, 2015, v. 9235, p. 577588   
dc.identifier.isbn  9783662480533   
dc.identifier.issn  03029743   
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 2428, 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 maxflows 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 allpairs 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 uv 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/9783662480540   
dc.rights  This work is licensed under a Creative Commons AttributionNonCommercialNoDerivatives 4.0 International License.   
dc.title  Efficient algorithm for computing all low st edge connectivities in directed graphs   
dc.type  Conference_Paper   
dc.description.nature  postprint   
dc.identifier.doi  10.1007/9783662480540   
dc.identifier.scopus  eid_2s2.084944593186   
dc.identifier.hkuros  254415   
dc.identifier.volume  9235   
dc.identifier.spage  577   
dc.identifier.epage  588   
dc.publisher.place  Germany   
dc.customcontrol.immutable  sml 151229   