Finding the edge connectivity of directed graphs

DOI10.1016/0196-6774(89)90024-2MaRDI QIDQ3815335zbMATH OpenOpenAlexFDO

Authors Yishay Mansour, Baruch Schieber

Publication date 1989

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-6774(89)90024-2

zbMATH Keywords

algorithmsdirected graphedge connectivity

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A matroid approach to finding edge connectivity and packing arborescences
• Efficient algorithm for computing all low s-t edge connectivities in directed graphs
• scientific article; zbMATH DE number 437577
• Faster algorithms for computing maximal 2-connected subgraphs in sparse directed graphs
• On computing the connectivities of graphs and digraphs

Cited in

(8)

• Extracting maximal information about sets of minimum cuts
• Determining uni-connectivity in directed graphs
• On testing single connectedness in directed graphs and some related problems
• Construction for bicritical graphs and \(k\)-extendable bipartite graphs
• Efficient algorithm for computing all low s-t edge connectivities in directed graphs
• 2-Edge Connectivity in Directed Graphs
• On the minimum number of inversions to make a digraph k-(arc-)strong
• Faster algorithms for rooted connectivity in directed graphs

This page was built for publication: Finding the edge connectivity of directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3815335)