Triangle counting in dynamic graph streams

DOI10.1007/s00453-015-0036-4zbMath1348.68294arXiv1404.4696OpenAlexW1608198436MaRDI QIDQ334947

Rasmus Pagh, Laurent Bulteau, Konstantin Kutzkov, Vincent Froese

Publication date: 1 November 2016

Published in: Algorithmica, Algorithm Theory – SWAT 2014 (Search for Journal in Brave)

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

zbMATH Keywords

streaming algorithmsrandomized approximation algorithmstriangle counting

Mathematics Subject Classification ID

Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items

Parameterized aspects of triangle enumeration

Uses Software

• DOULION

Cites Work

• Unnamed Item
• Colorful triangle counting and a \textsc{MapReduce} implementation
• Finding and counting given length cycles
• Universal classes of hash functions
• On randomized one-round communication complexity
• Triangle Sparsifiers
• Tabulation-Based 5-Independent Hashing with Applications to Linear Probing and Second Moment Estimation
• Statistical mechanics of complex networks
• Approximate Counting of Cycles in Streams
• Counting Arbitrary Subgraphs in Data Streams
• A random graph model for massive graphs
• Uniform Hashing in Constant Time and Optimal Space
• Sampling in dynamic data streams and applications
• The Power of Simple Tabulation Hashing
• Multiplying matrices faster than coppersmith-winograd
• Computing and Combinatorics
• Efficient Triangle Counting in Large Graphs via Degree-Based Vertex Partitioning