Counting Triangles under Updates in Worst-Case Optimal Time

DOI10.4230/LIPICS.ICDT.2019.4OpenAlexW2964216306MaRDI QIDQ5091114FDOQ5091114

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

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)

zbMATH Keywords

incremental view maintenanceamortized analysisdata skew

Mathematics Subject Classification ID

Database theory (68P15)

Cites Work

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

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)