Counting Arbitrary Subgraphs in Data Streams

DOI10.1007/978-3-642-31585-5_53zbMath1367.68213OpenAlexW2137778430MaRDI QIDQ3167047

Kurt Mehlhorn, Daniel M. Kane, He Sun, Thomas Sauerwald

Publication date: 1 November 2012

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

Full work available at URL: https://doi.org/10.1007/978-3-642-31585-5_53

zbMATH Keywords

network analysisdata streamssubgraph counting

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (10)

On triangle estimation using tripartite independent set queries ⋮ Triangle counting in dynamic graph streams ⋮ Approximately Counting Triangles in Sublinear Time ⋮ Unnamed Item ⋮ On Approximating the Number of $k$-Cliques in Sublinear Time ⋮ Sublinear-time algorithms for counting star subgraphs via edge sampling ⋮ Unnamed Item ⋮ A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling ⋮ Optimal lower bounds for matching and vertex cover in dynamic graph streams ⋮ Clique Counting in MapReduce

This page was built for publication: Counting Arbitrary Subgraphs in Data Streams