Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams

DOI10.1145/2746539.2746592zbMath1321.05253arXiv1504.02268OpenAlexW1977458171MaRDI QIDQ2941505

Sayan Bhattacharya, Danupon Nanongkai, Charalampos E. Tsourakakis, Monika R. Henzinger

Publication date: 21 August 2015

Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

streaming algorithmsdynamic graph algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Density (toughness, etc.) (05C42)

Related Items (8)

Graph sketching and streaming: new approaches for analyzing massive graphs ⋮ Finding dense subgraphs with maximum weighted triangle density ⋮ On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition ⋮ Finding lasting dense subgraphs ⋮ Finding densest \(k\)-connected subgraphs ⋮ Dynamic graph stream algorithms in \(o(n)\) space ⋮ Optimality of linear sketching under modular updates ⋮ Better streaming algorithms for the maximum coverage problem

Uses Software

• Graphs

Cites Work

• Unnamed Item
• Ramsey partitions and proximity data structures
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming

This page was built for publication: Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams