New streaming algorithms for counting triangles in graphs

DOI10.1007/11533719_72MaRDI QIDQ5716993zbMATH OpenOpenAlexFDO

Authors Hossein Jowhari, Mohammad Ghodsi

Publication date 11 January 2006

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11533719

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Approximation algorithms (68W25)

Recommendations

• How hard is counting triangles in the streaming model?
• A second look at counting triangles in graph streams
• A hybrid sampling scheme for triangle counting

Cited in

(28)

• New bounds for the CLIQUE-GAP problem using graph decomposition theory
• Graph sampling with applications to estimating the number of pattern embeddings and the parameters of a statistical relational model
• Intractability of min- and max-cut in streaming graphs
• A second look at counting triangles in graph streams (corrected)
• Corrigendum to: ``A second look at counting triangles in graph streams
• Clique counting in MapReduce: algorithms and experiments
• New bounds for the CLIQUE-GAP problem using graph decomposition theory
• Approximate counting of cycles in streams
• Colorful triangle counting and a \textsc{MapReduce} implementation
• Optimal sampling from sliding windows
• A hybrid sampling scheme for triangle counting
• Approximately counting triangles in sublinear time
• scientific article; zbMATH DE number 6862103 (Why is no real title available?)
• scientific article; zbMATH DE number 2119719 (Why is no real title available?)
• A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
• Counting Triangles under Updates in Worst-Case Optimal Time
• On approximating the number of k-cliques in sublinear time
• How hard is counting triangles in the streaming model?
• Efficient triangle counting in large graphs via degree-based vertex partitioning
• scientific article; zbMATH DE number 7758324 (Why is no real title available?)
• Fast approximate counting of cycles
• Counting simplices in hypergraph streams
• Towards optimal dynamic indexes for approximate (and exact) triangle counting
• Near uniform triangle sampling over adjacency list graph streams
• Recent advances in fully dynamic graph algorithms (invited talk)
• A second look at counting triangles in graph streams
• On triangle estimation using tripartite independent set queries
• Main-memory triangle computations for very large (sparse (power-law)) graphs

This page was built for publication: New streaming algorithms for counting triangles in graphs

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