Tight bounds on vertex connectivity under vertex sampling

DOI10.1137/1.9781611973730.133zbMATH Open1371.05154OpenAlexW4246355065MaRDI QIDQ5363076FDOQ5363076

Authors: Keren Censor-Hillel, Mohsen Ghaffari, George Giakkoupis, Bernhard Haeupler, Fabian Kuhn 

Publication date: 5 October 2017

Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973730.133

Recommendations

• Tight Bounds on Vertex Connectivity Under Sampling
• scientific article; zbMATH DE number 1670666
• A probabilistic algorithm for vertex connectivity of graphs
• Breaking quadratic time for small vertex connectivity and an approximation scheme

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Cited In (5)

• Computing Vertex Connectivity: New Bounds from Old Techniques
• Sampling to provide or to bound: With applications to fully dynamic graph algorithms
• On the Complexity of Sampling Vertices Uniformly from a Graph
• Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs
• Tight Bounds on Vertex Connectivity Under Sampling

This page was built for publication: Tight bounds on vertex connectivity under vertex sampling

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