File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Efficient algorithm for computing all low s-t edge connectivities in directed graphs

TitleEfficient algorithm for computing all low s-t edge connectivities in directed graphs
Authors
Issue Date2015
PublisherSpringer 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?
AbstractGiven 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.
DescriptionLNCS v. 9235 entitled: Mathematical Foundations of Computer Science 2015: 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part 2
Persistent Identifierhttp://hdl.handle.net/10722/219233
ISBN
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252

 

DC FieldValueLanguage
dc.contributor.authorWu, X-
dc.contributor.authorZhang, C-
dc.date.accessioned2015-09-18T07:18:24Z-
dc.date.available2015-09-18T07:18:24Z-
dc.date.issued2015-
dc.identifier.citationThe 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.isbn978-366248053-3-
dc.identifier.issn0302-9743-
dc.identifier.urihttp://hdl.handle.net/10722/219233-
dc.descriptionLNCS 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.abstractGiven 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.languageeng-
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/-
dc.relation.ispartofLecture Notes in Computer Science-
dc.rightsThe final publication is available at Springer via http://dx.doi.org/10.1007/978-3-662-48054-0-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.titleEfficient algorithm for computing all low s-t edge connectivities in directed graphs-
dc.typeConference_Paper-
dc.description.naturepostprint-
dc.identifier.doi10.1007/978-3-662-48054-0-
dc.identifier.scopuseid_2-s2.0-84944593186-
dc.identifier.hkuros254415-
dc.identifier.volume9235-
dc.identifier.spage577-
dc.identifier.epage588-
dc.publisher.placeGermany-
dc.customcontrol.immutablesml 151229-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats