7

[2302.05951] Fully Dynamic Exact Edge Connectivity in Sublinear Time

 2 years ago
source link: https://arxiv.org/abs/2302.05951
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

[Submitted on 12 Feb 2023]

Fully Dynamic Exact Edge Connectivity in Sublinear Time

Download PDF

Given a simple n-vertex, m-edge graph G undergoing edge insertions and deletions, we give two new fully dynamic algorithms for exactly maintaining the edge connectivity of G in \tilde{O}(n) worst-case update time and \tilde{O}(m^{1-1/16}) amortized update time, respectively. Prior to our work, all dynamic edge connectivity algorithms assumed bounded edge connectivity, guaranteed approximate solutions, or were restricted to edge insertions only. Our results answer in the affirmative an open question posed by Thorup [Combinatorica'07].

Subjects: Data Structures and Algorithms (cs.DS)
Cite as: arXiv:2302.05951 [cs.DS]
  (or arXiv:2302.05951v1 [cs.DS] for this version)
  https://doi.org/10.48550/arXiv.2302.05951

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK