Concepedia

Graph Connectivity Queries

Graph Connectivity Queries is a computational framework within graph theory that determines whether two vertices in a dynamic graph remain connected through a sequence of edge insertions and deletions, using disjoint set union data structures to efficiently manage and query connected components.

55

Publications

2.1K

Citations

107

Authors

75

Institutions

Publications per year

2017–2026

14

Parents

Publications

55

Dynamic graph connectivity in polylogarithmic worst case time

Bruce M. Kapron, Valerie King, Ben Mountjoy · Symposium on Discrete Algorithms · 2013 · 141 citations

, , +16

Fully dynamic biconnectivity and transitive closure

Monika Henzinger, Valerie King · 2002 · 135 citations

, , +12

Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees

Greg N. Frederickson · SIAM Journal on Computing · 1997 · 103 citations

, , +15

Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees

Greg N. Frederickson · 2002 · 102 citations

, , +15

A fully dynamic reachability algorithm for directed graphs with an almost linear update time

Liam Roditty, Uri Zwick · 2004 · 91 citations

, , +13

1–5 of 55

Authors

107

  1. LR
    Liam Roditty

    Bar-Ilan University, Israel

    5 publications · 188 citations

    5

    h-index

  2. VK
    Valerie King

    University of Victoria, Canada

    4 publications · 375 citations

    4

    h-index

  3. TM
    Timothy M. Chan

    University of Waterloo, Canada

    3 publications · 76 citations

    3

    h-index

  4. SP
    Seth Pettie

    University of Michigan, United States

    3 publications · 130 citations

    3

    h-index

  5. SS
    Subhash Suri

    University of California, Santa Barbara, United States

    2 publications · 47 citations

    2

    h-index

1–5 of 107

Institutions

75

  1. University of Waterloo

    Waterloo, Canada

    5 h-index

    5 publications

    161 citations

  2. University of Edinburgh

    Edinburgh, United Kingdom

    4 h-index

    5 publications

    214 citations

  3. Institut national de recherche en sciences et technologies du numérique

    Le Chesnay-Rocquencourt, France

    4 h-index

    5 publications

    170 citations

  4. University of Copenhagen

    Copenhagen, Denmark

    3 h-index

    3 publications

    65 citations

  5. University of Michigan

    Ann Arbor, United States

    3 h-index

    6 publications

    260 citations

  6. Georgia Institute of Technology

    Atlanta, United States

    3 h-index

    9 publications

    267 citations

  7. Siemens (Hungary)

    Budapest, Hungary

    2 h-index

    2 publications

    47 citations

  8. Nokia (United States)

    Coppell, United States

    2 h-index

    3 publications

    50 citations

1–8 of 75

Venues

  1. SIAM Journal on Computing

    7 publications · 260 citations

    7

    h-index

  2. Proceedings of the VLDB Endowment

    PVLDB · 3 publications · 71 citations

    3

    h-index

  3. Algorithmica

    2 publications · 62 citations

    2

    h-index

  4. Journal of the ACM

    JACM · 2 publications · 100 citations

    2

    h-index

  5. Information

    1 publications · 12 citations

    1

    h-index

1–5