A probabilistic algorithm for vertex connectivity of graphs

DOI10.1016/0020-0190(82)90046-1MaRDI QIDQ1167545zbMATH OpenOpenAlexFDO

Authors S. Singh

Publication date 1982

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(82)90046-1

zbMATH Keywords

complexitynetwork flowsparse graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Connectivity (05C40)

Recommendations

• Bounds on probability of connectedness of a random graph
• On the connectedness of a random graph
• scientific article; zbMATH DE number 4205985
• scientific article; zbMATH DE number 986986
• VERTEX DECOMPOSITION TO CALCULATE THE NETWORK PROBABILISTIC CONNECTIVITY
• scientific article; zbMATH DE number 3876622
• scientific article; zbMATH DE number 3854438
• scientific article; zbMATH DE number 4101220
• Connectedness of certain random graphs

Cites work

• Network Flow and Testing Graph Connectivity

Cited in

(9)

• Engineering Nearly Linear-time Algorithms for Small Vertex Connectivity
• Improved algorithms for graph four-connectivity
• Breaking quadratic time for small vertex connectivity and an approximation scheme
• Graph connectivity, partial words, and a theorem of Fine and Wilf
• VERTEX DECOMPOSITION TO CALCULATE THE NETWORK PROBABILISTIC CONNECTIVITY
• Directed \(s\)-\(t\) numberings, rubber bands, and testing digraph \(k\)-vertex connecitivity
• Tight bounds on vertex connectivity under vertex sampling
• Using expander graphs to find vertex connectivity
• Finding a small vertex cut on distributed networks

This page was built for publication: A probabilistic algorithm for vertex connectivity of graphs

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