Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection
From MaRDI portal
Publication:4972298
DOI10.1137/17M1159014zbMath1493.68268arXiv1604.03661MaRDI QIDQ4972298
Dana Ron, Talya Eden, C. Seshadhri
Publication date: 25 November 2019
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1604.03661
degeneracydegree distributionapproximation algorithmsarboricitysublinear time algorithmsdegree moments
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- plfit
- The method of moments and degree distributions for network models
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
- The space complexity of approximating the frequency moments
- Relaxing the uniformity and independence assumptions using the concept of fractal dimension
- Sublinear-time algorithms for counting star subgraphs via edge sampling
- Structural sparsity
- Why do simple algorithms for triangle enumeration work in the real world?
- Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time
- Emergence of Scaling in Random Networks
- Counting Stars and Other Small Subgraphs in Sublinear-Time
- Edge-Disjoint Spanning Trees of Finite Graphs
- Approximating average parameters of graphs
- Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
- Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs
- Power-Law Distributions in Empirical Data
- Arboricity and Subgraph Listing Algorithms
- Smallest-last ordering and clustering and graph coloring algorithms
- Winners don't take all: Characterizing the competition for links on the web
- Algorithmic Complexity of Power Law Networks
- Approximately Counting Triangles in Sublinear Time
- Approximating the distance to properties in bounded-degree and general sparse graphs
- Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection
- Local Graph Partitions for Approximation and Testing
- An improved constant-time approximation algorithm for maximum~matchings
- Approximating the Minimum Spanning Tree Weight in Sublinear Time
- On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
- Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
- Decomposition of Finite Graphs Into Forests
