Sampling arbitrary subgraphs exactly uniformly in sublinear time

DOI10.4230/LIPICS.ICALP.2020.45MaRDI QIDQ6842531zbMATH OpenFDO

Authors Hendrik Fichtenberger, Mingze Gao, Pan Peng

Publication date 18 March 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2020.45

zbMATH Keywords

graph algorithmsgraph samplingsublinear-time algorithms

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Approximately counting triangles in sublinear time
• Approximating average parameters of graphs
• Estimating graph parameters via random walks with restarts
• Lower bounds for approximating graph parameters via communication complexity
• On approximating the number of k-cliques in sublinear time
• On sampling edges almost uniformly
• On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
• Sublinear-time algorithms for counting star subgraphs via edge sampling
• The arboricity captures the complexity of sampling edges
• Tight Bounds for Testing Bipartiteness in General Graphs
• What can be sampled locally?

Cited in

(3)

• Join sampling under acyclic degree constraints and (cyclic) subgraph sampling
• Join and subgraph sampling under degree constraints
• Near uniform triangle sampling over adjacency list graph streams

This page was built for publication: Sampling arbitrary subgraphs exactly uniformly in sublinear time

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