• Fulltext

       

        Click here to view fulltext PDF


      Permanent link:
      https://www.ias.ac.in/article/fulltext/reso/027/08/1443-1451

    • Keywords

       

      Dynamic graphs, upper bounds, lower bounds, conditional lower bounds.

    • Abstract

       

      We present a three-part article comprising a survey of some of the extensively used techniques in the dynamic graph model that have appeared recently in the computer science commu­nity. This article presents the first part of the survey outlin­ing the motivation for research in dynamic graph algorithms and an introduction to dynamic graphs. In the second part of the survey, we will present a set of techniques to prove up­per bounds for dynamic graph problems. In the third part of the survey, we will present a set of techniques to prove lower 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. Though classic problems like coloring, matching, independent set, and many more are extensively studied for static graphs, we are still far from obtaining a complete set of lower bounds and upper bounds results for their dynamic graph counterparts. Along with theoretical advances, the techniques used in dynamic graphs need attention from an implementation perspective. The practical potential of these techniques is yet to be explored. We invite undergraduate researchers and programmers to consider an efficient implementation of these techniques through this three-part survey. The survey can also be used to understand the first algorithms for several recent dynamic graph algorithms.

    • Author Affiliations

       

      Manas Jyoti Kashyop1 N S Narayanaswamy2

      1. The Instit te of Mathematical Sciences Chennai, India.
      2. Department of CSE, IIT Madras Chennai, India.
    • Dates

       

© 2021-2022 Indian Academy of Sciences, Bengaluru.