Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Dynamic Connectivity:
TR16-167 | 1st November 2016
Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao

New Randomized Data Structure Lower Bounds for Dynamic Graph Connectivity

Revisions: 1

The problem of dynamic connectivity in graphs has been extensively studied in the cell probe model. The task is to design a data structure that supports addition of edges and checks connectivity between arbitrary pair of vertices. Let $w, t_q, t_u$ denote the cell width, expected query time and worst ... more >>>

ISSN 1433-8092 | Imprint