Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs

DOI10.1145/3596495arXiv2007.12102OpenAlexW4381856690MaRDI QIDQ6051991

Marco Bressan

Publication date: 23 October 2023

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

Full work available at URL: https://arxiv.org/abs/2007.12102

zbMATH Keywords

random walkssublinear algorithmssubgraph sampling

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Faster algorithms for counting subgraphs in sparse graphs
• On the triangle clique cover and \(K_t\) clique cover problems
• Mixing time bounds for graphlet random walks
• Arboricity and Subgraph Listing Algorithms
• Smallest-last ordering and clustering and graph coloring algorithms
• Color-coding
• Approximately Counting Triangles in Sublinear Time
• Tight Bounds for Testing Bipartiteness in General Graphs
• A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
• On Approximating the Number of $k$-Cliques in Sublinear Time
• On Sampling Edges Almost Uniformly
• Counting Subgraphs in Degenerate Graphs
• Efficient and near-optimal algorithms for sampling connected subgraphs
• Sampling Multiple Edges Efficiently
• Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time

This page was built for publication: Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs