Efficient and near-optimal algorithms for sampling connected subgraphs

DOI10.1145/3406325.3451042MaRDI QIDQ6065238zbMATH OpenOpenAlexFDO

Authors Marco Bressan

Publication date 14 November 2023

Published in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3406325.3451042

zbMATH Keywords

random walkssubgraph samplingsublinear algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited in

(9)

• Sublinear-time algorithms for counting star subgraphs via edge sampling
• Scalable Uniform Graph Sampling by Local Computation
• Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms
• Sampling to provide or to bound: With applications to fully dynamic graph algorithms
• Tight Bounds on Vertex Connectivity Under Sampling
• Sublinear Random Access Generators for Preferential Attachment Graphs
• Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs
• Sampling Multiple Edges Efficiently
• Fast and perfect sampling of subgraphs and polymer systems

This page was built for publication: Efficient and near-optimal algorithms for sampling connected subgraphs

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