An Invitation to Dynamic Graph Problems: Lower Bounds -- III

Resonance

article

Manas Jyoti Kashyop¹  N S Narayanaswamy² 

[1] The Institute of Mathematical Sciences;Department of CSE

关键词: Dynamic graph algorithms;    adversary;    cell-probe lower bounds;    conditional lower bound.;   

DOI  :  10.1007/s12045-022-1471-6

学科分类：社会科学、人文和艺术（综合）

来源: Springer

【 摘 要 】

We present a three-part paper consisting of a survey of some of the extensively used techniques in the dynamic graph model that have appeared recently in the computer science community. In this third part of the three-part survey paper, we present a set of techniques to prove lower bounds for dynamic graph problems. In the first part\mfnote{\textit{Resonance}, Vol.27, No.8, pp.1443--1451, August 2022.} of the survey, we presented the motivation for research in dynamic graph algorithms and an introduction to dynamic graphs. In the second part\mfnote{\textit{Resonance}, Vol.27, No.9, pp.1607-1624, September 2022.} of the survey, we presented a set of techniques to prove upper bounds for dynamic graph problems.A dynamic graph is a graph that has a fixed vertex set and an evolving edge set. The edge set keeps changing due to the insertion of a new edge or the deletion of an existing edge. Research in dynamic graphs has succeeded in obtaining efficient upper bounds for an extensive collection of problems. However, there are problems of stubborn nature. Such complex problems lead to the investigation of lower bounds.

【 授权许可】

Others