Fully Dynamic Exact Edge Connectivity in Sublinear Time

被引：0

作者：

Goranci, Gramoz ^{[1
]}

Henzinger, Monika ^{[2
]}

Nanongkai, Danupon ^{[3
,4
,5
]}

Saranurak, Thatchaphol ^{[6
]}

Thorup, Mikkel ^{[4
]}

Wulff-Nilsen, Christian ^{[4
]}

机构：

[1] Swiss Fed Inst Technol, Inst Theoret Studies, Zurich, Switzerland

[2] Univ Vienna, Fac Comp Sci, Vienna, Austria

[3] Max Planck Inst Informat, Saarbrucken, Germany

[4] Univ Copenhagen, Copenhagen, Denmark

[5] KTH, Stockholm, Sweden

[6] Univ Michigan, Ann Arbor, MI USA

来源：

PROCEEDINGS OF THE 2023 ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA | 2023年

基金：

奥地利科学基金会; 欧洲研究理事会;

关键词：

GRAPH ALGORITHMS; MINIMUM CUT; FASTER; TREES;

D O I：

暂无

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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 (O) over tilde (n) worst-case update time and (O) over tilde (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].

引用

页码：70 / 86

页数：17

共 57 条

[1]

Ahn KJ, 2009, LECT NOTES COMPUT SC, V5556, P328

[2]

Ahn KookJin., 2012, P 23 ANN ACM SIAM S, P459, DOI DOI 10.1137/1.9781611973099.40

[3] Maintaining Information in Fully Dynamic Trees with Top Trees [J].

Alstrup, Stephen ;

Holm, Jacob ;

De Lichtenberg, Kristian ;

Thorup, Mikkel .

ACM TRANSACTIONS ON ALGORITHMS, 2005, 1 (02) :243-264

[4]

Assadi S, 2021, Simplicity in Algori, P172

[5]

Bernstein A., 2022, LIPIcs, V229

[6]

Bhardwaj Nalin, 2020, SCAND S WORKSH ALG T

[7] A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond [J].

Chuzhoy, Julia ;

Gao, Yu ;

Li, Jason ;

Nanongkai, Danupon ;

Peng, Richard ;

Saranurak, Thatchaphol .

2020 IEEE 61ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2020), 2020, :1158-1167

[8] A New Algorithm for Decremental Single-Source Shortest Paths with Applications to Vertex-Capacitated Flow and Cut Problems [J].

Chuzhoy, Julia ;

Khanna, Sanjeev .

PROCEEDINGS OF THE 51ST ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '19), 2019, :389-400

[9] A unifying framework for l0-sampling algorithms [J].

Cormode, Graham ;

Firmani, Donatella .

DISTRIBUTED AND PARALLEL DATABASES, 2014, 32 (03) :315-335

[10] Distributed Edge Connectivity in Sublinear Time [J].

Daga, Mohit ;

Henzinger, Monika ;

Nanongkai, Danupon ;

Saranurak, Thatchaphol .

PROCEEDINGS OF THE 51ST ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '19), 2019, :343-354

← 1 2 3 4 5 6 →