Counting arbitrary subgraphs in data streams

DOI10.1007/978-3-642-31585-5_53MaRDI QIDQ3167047zbMATH OpenOpenAlexFDO

Authors Daniel M. Kane, K. Mehlhorn, Thomas Sauerwald, He Sun

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

data streamsnetwork analysissubgraph counting

Mathematics Subject Classification ID

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

Recommendations

• Approximate counting of cycles in streams
• scientific article; zbMATH DE number 6862103
• How hard is counting triangles in the streaming model?

Cited in

(18)

• Sublinear-time algorithms for counting star subgraphs via edge sampling
• Discovering rare categories from graph streams
• Clique counting in MapReduce: algorithms and experiments
• Approximate counting of cycles in streams
• Approximately counting triangles in sublinear time
• A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
• Optimal lower bounds for matching and vertex cover in dynamic graph streams
• On approximating the number of k-cliques in sublinear time
• scientific article; zbMATH DE number 7650137 (Why is no real title available?)
• scientific article; zbMATH DE number 7758324 (Why is no real title available?)
• Fast approximate counting of cycles
• Counting simplices in hypergraph streams
• Brief announcement: improved massively parallel triangle counting in O(1) rounds
• Even the easiest(?) Graph coloring problem is not easy in streaming!
• Towards optimal dynamic indexes for approximate (and exact) triangle counting
• Near uniform triangle sampling over adjacency list graph streams
• On triangle estimation using tripartite independent set queries
• Sequential stratified regeneration: \textit{MCMC} for large state spaces with an application to subgraph count estimation

This page was built for publication: Counting arbitrary subgraphs in data streams

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