The arboricity captures the complexity of sampling edges

DOI10.4230/LIPICS.ICALP.2019.52MaRDI QIDQ5091207zbMATH OpenFDO

Authors Talya Eden, Dana Ron, Will Rosenbaum

Publication date 21 July 2022

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

zbMATH Keywords

arboricitygraph algorithmssamplingsublinear-time algorithms

Mathematics Subject Classification ID

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

Recommendations

• On sampling edges almost uniformly
• Sublinear time estimation of degree distribution moments: the arboricity connection
• A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling

Cites work

• A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
• Approximately counting triangles in sublinear time
• Approximating average parameters of graphs
• Augmenting \(k\)-core generation with preferential attachment
• Bounded Arboricity to Determine the Local Structure of Sparse Graphs
• Counting stars and other small subgraphs in sublinear-time
• Edge-Disjoint Spanning Trees of Finite Graphs
• Emergence of Scaling in Random Networks
• Enumerating and generating labeled \(k\)-degenerate graphs
• scientific article; zbMATH DE number 7204459 (Why is no real title available?)
• 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
• Property testing lower bounds via communication complexity
• Sublinear-time algorithms for counting star subgraphs via edge sampling
• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition

Cited in

(5)

• Sampling arbitrary subgraphs exactly uniformly in sublinear time
• Testing some first-order logic properties on sparse graphs
• Testing C_k-freeness in bounded-arboricity graphs
• Testing triangle freeness in the general model in graphs with arboricity \(O(\sqrt{n})\)
• Tolerant testers for subgraph-freeness

This page was built for publication: The arboricity captures the complexity of sampling edges

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