Counting Triangles under Updates in Worst-Case Optimal Time

DOI10.4230/LIPIcs.ICDT.2019.4OpenAlexW2964216306MaRDI QIDQ5091114

Miloš Nikolić, Haozhe Zhang, Ahmet Kara, Dan Olteanu, Hung Quang 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)

Related Items (4)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding and counting given length cycles
• A second look at counting triangles in graph streams (corrected)
• The dynamic descriptive complexity of \(k\)-clique
• Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
• Approximately Counting Triangles in Sublinear Time
• Algorithmic Aspects of Parallel Data Processing
• Computing and Combinatorics

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