How Hard Is Counting Triangles in the Streaming Model?

DOI10.1007/978-3-642-39206-1_21zbMath1336.68283arXiv1304.1458OpenAlexW1799685217MaRDI QIDQ5326565

Dan Vilenchik, Vladimir Braverman, Rafail Ostrovsky

Publication date: 6 August 2013

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items (3)

A second look at counting triangles in graph streams (corrected) ⋮ A second look at counting triangles in graph streams ⋮ A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling

This page was built for publication: How Hard Is Counting Triangles in the Streaming Model?