Counting Triangles under Updates in Worst-Case Optimal Time

DOI10.4230/LIPICS.ICDT.2019.4MaRDI QIDQ5091114zbMATH OpenOpenAlexFDO

Authors Ahmet Kara, Miloš Nikolić, Dan Olteanu, Haozhe Zhang, Hung Q. Ngo

Publication date 21 July 2022

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

zbMATH Keywords

incremental view maintenanceamortized analysisdata skew

Mathematics Subject Classification ID

Database theory (68P15)

Recommendations

• Approximately counting triangles in sublinear time
• An Optimal Algorithm for Triangle Counting in the Stream
• Computing and Combinatorics
• Efficiently enumerating minimal triangulations
• An efficient algorithm for enumeration of triangulations
• A second look at counting triangles in graph streams
• A second look at counting triangles in graph streams (corrected)

Cites work

• scientific article; zbMATH DE number 2119719 (Why is no real title available?)
• A second look at counting triangles in graph streams (corrected)
• Algorithmic aspects of parallel data processing
• Answering FO+MOD queries under updates on bounded degree databases
• Answering UCQs under updates and in the presence of integrity constraints
• Approximately counting triangles in sublinear time
• Computing and Combinatorics
• Finding and counting given length cycles
• The dynamic descriptive complexity of k-clique
• Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture

Cited in

(4)

• Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries
• General space-time tradeoffs via relational queries
• On linear algebraic algorithms for the subgraph matching problem and its variants
• Range updates and range sum queries on multidimensional points with monoid weights

This page was built for publication: Counting Triangles under Updates in Worst-Case Optimal Time

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