Tight Bounds on Vertex Connectivity Under Sampling

DOI10.1145/3086465MaRDI QIDQ4962652zbMATH OpenOpenAlexFDO

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

Publication date 5 November 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/hal-01635743/file/talg2017kvc.pdf

zbMATH Keywords

graph samplingvertex connectivity

Mathematics Subject Classification ID

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

Recommendations

• Tight bounds on vertex connectivity under vertex sampling
• The hardness of sampling connected subgraphs
• On the Complexity of Sampling Vertices Uniformly from a Graph
• Efficient and near-optimal algorithms for sampling connected subgraphs
• Uniform sampling of directed and undirected graphs conditional on vertex connectivity
• Random contractions and sampling for hypergraph and hedge connectivity
• Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs
• Bounds on probability of connectedness of a random graph
• Estimating the number of connected components in a graph via subgraph sampling
• Computing Vertex Connectivity: New Bounds from Old Techniques

Cited in

(8)

• Sampling to provide or to bound: With applications to fully dynamic graph algorithms
• On the Complexity of Sampling Vertices Uniformly from a Graph
• scientific article; zbMATH DE number 7559095 (Why is no real title available?)
• Tight bounds on vertex connectivity under vertex sampling
• Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs
• Cycle lengths in randomly perturbed graphs
• Rigid partitions: from high connectivity to random graphs
• Connected partitions via connected dominating sets

This page was built for publication: Tight Bounds on Vertex Connectivity Under Sampling

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