Tight bounds on vertex connectivity under vertex sampling

DOI10.1137/1.9781611973730.133MaRDI QIDQ5363076zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

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)