Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ https://epubs.siam.o...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
https://epubs.siam.org/doi/pdf...
Part of book or chapter of book
Data sources: UnpayWall
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
https://doi.org/10.1137/1.9781...
Part of book or chapter of book . 2021 . Peer-reviewed
Data sources: Crossref
https://dx.doi.org/10.48550/ar...
Article . 2020
License: arXiv Non-Exclusive Distribution
Data sources: Datacite
versions View all 3 versions
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

The Expander Hierarchy and its Applications to Dynamic Graph Algorithms

Authors: Goranci, Gramoz; Räcke, Harald; Saranurak, Thatchaphol; Tan, Zihan;

The Expander Hierarchy and its Applications to Dynamic Graph Algorithms

Abstract

We introduce a notion for hierarchical graph clustering which we call the expander hierarchy and show a fully dynamic algorithm for maintaining such a hierarchy on a graph with $n$ vertices undergoing edge insertions and deletions using $n^{o(1)}$ update time. An expander hierarchy is a tree representation of graphs that faithfully captures the cut-flow structure and consequently our dynamic algorithm almost immediately implies several results including: (1) The first fully dynamic algorithm with $n^{o(1)}$ worst-case update time that allows querying $n^{o(1)}$-approximate conductance, $s$-$t$ maximum flows, and $s$-$t$ minimum cuts for any given $(s,t)$ in $O(\log^{1/6} n)$ time. Our results are deterministic and extend to multi-commodity cuts and flows. The key idea behind these results is a fully dynamic algorithm for maintaining a tree flow sparsifier, a notion introduced by R��cke [FOCS'02] for constructing competitive oblivious routing schemes. (2) A deterministic fully dynamic connectivity algorithm with $n^{o(1)}$ worst-case update time. This significantly simplifies the recent algorithm by Chuzhoy et al.~that uses the framework of Nanongkai et al. [FOCS'17]. (3) The first non-trivial deterministic fully dynamic treewidth decomposition algorithm on constant-degree graphs with $n^{o(1)}$ worst-case update time that maintains a treewidth decomposition of width $\text{tw}(G)\cdot n^{o(1)}$ where $\text{tw}(G)$ denotes the treewidth of the current graph. Our technique is based on a new stronger notion of the expander decomposition, called the boundary-linked expander decomposition. This decomposition is more robust against updates and better captures the clustering structure of graphs. Given that the expander decomposition has proved extremely useful in many fields, we expect that our new notion will find more future applications.

Keywords

FOS: Computer and information sciences, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS)

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    19
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Top 10%
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Top 10%
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Top 10%
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
19
Top 10%
Top 10%
Top 10%
Green
bronze