research-article

Open access

Improved Worst-Case Deterministic Parallel Dynamic Minimum Spanning Forest

Authors:

Tsvi Kopelowitz,

Yair RosenmutterAuthors Info & Claims

SPAA '18: Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures

Pages 333 - 341

https://doi.org/10.1145/3210377.3210403

Published: 11 July 2018 Publication History

Abstract

This paper gives a new deterministic algorithm for the dynamic Minimum Spanning Forest (MSF) problem in the EREW PRAM model, where the goal is to maintain a MSF of a weighted graph with n vertices and m edges while supporting edge insertions and deletions. We show that one can solve the dynamic MSF problem using $O(\sqrt n)$ processors and $O(łog n)$ worst-case update time, for a total of $O(\sqrt n łog n)$ work. This improves on the work of Ferragina [IPPS 1995] which costs $O(łog n)$ worst-case update time and $O(n^2/3 łog\fracm n )$ work.

References

[1]

Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, and Richard Peng. On fully dynamic graph sparsifiers. In IEEE 57th Annual Symposium on Foundations of Computer Science, (FOCS), pages 335--344, 2016.

[2]

Sajal K. Das and Paolo Ferragina. An o(n) work EREW parallel algorithm for updating MST. In 2'nd Annual European Symposium on Algorithms, (ESA), pages 331--342, 1994.

Digital Library

[3]

David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Amnon Nissenzweig. Sparsification-a technique for speeding up dynamic graph algorithms (extended abstract). In 33rd Annual Symposium on Foundations of Computer Science, (FOCS), pages 60--69, 1992.

Digital Library

[4]

David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Amnon Nissenzweig. Sparsification - a technique for speeding up dynamic graph algorithms. J. ACM, 44(5):669--696, 1997.

Digital Library

[5]

Paolo Ferragina. An EREW PRAM fully-dynamic algorithm for MST. In The 9th International Parallel Processing Symposium, (IPPS), pages 93--100, 1995.

Digital Library

[6]

Greg N. Frederickson. Data structures for on-line updating of minimum spanning trees, with applications. SIAM J. Comput., 14(4):781--798, 1985.

Digital Library

[7]

D. Gibb, B. M. Kapron, V. King, and N. Thorn. Dynamic graph connectivity with improved worst case update time and sublinear space. CoRR, abs/1509.06464, 2015.

[8]

Monika Rauch Henzinger and Valerie King. Maintaining minimum spanning trees in dynamic graphs. In Automata, Languages and Programming, 24th International Colloquium, (ICALP), pages 594--604, 1997.

Digital Library

[9]

Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM, 48(4):723--760, 2001.

Digital Library

[10]

Jacob Holm, Eva Rotenberg, and Christian Wulff-Nilsen. Faster fully-dynamic minimum spanning forest. In Algorithms - 23rd Annual European Symposium, (ESA), Proceedings, pages 742--753, 2015.

[11]

Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, and Seth Pettie. Fully dynamic connectivity in O(log n(log log n)(^mbox2)) amortized expected time. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), pages 510--520, 2017.

Digital Library

[12]

Joseph J´aJ´a. An introduction to parallel algorithms. In Addison-Wesley, 1992.

Digital Library

[13]

Bruce M. Kapron, Valerie King, and Ben Mountjoy. Dynamic graph connectivity in polylogarithmic worst case time. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), pages 1131--1142, 2013.

Digital Library

[14]

Casper Kejlberg-Rasmussen, Tsvi Kopelowitz, Seth Pettie, and Mikkel Thorup. Faster worst case deterministic dynamic connectivity. In 24th Annual European Symposium on Algorithms, (ESA), pages 53:1--53:15, 2016.

[15]

Tsvi Kopelowitz, Ely Porat, and Yair Rosenmutter. Improved worst-case deterministic parallel dynamic minimum spanning forest. CoRR, abs/1805.06151, 2018.

Digital Library

[16]

W. Liang and B.D. McKay. Fully dynamic maintenance of minimum spanning trees by using a sublinear number of processors. In Unpublished Manuscripts, 1994.

[17]

Danupon Nanongkai and Thatchaphol Saranurak. Dynamic spanning forest with worst-case update time: adaptive, las vegas, and o(n(^mbox1/2 - (ε)))-time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, (STOC), pages 1122--1129, 2017.

Digital Library

[18]

Danupon Nanongkai, Thatchaphol Saranurak, and Christian Wulff-Nilsen. Dynamic minimum spanning forest with subpolynomial worst-case update time. In 58th IEEE Annual Symposium on Foundations of Computer Science, (FOCS), pages 950--961, 2017.

[19]

Mihai ¶atrascu and Erik D. Demaine. Logarithmic lower bounds in the cell-probe model. SIAM J. Comput., 35(4):932--963, 2006.

Digital Library

[20]

Daniel Dominic Sleator and Robert Endre Tarjan. A data structure for dynamic trees. J. Comput. Syst. Sci., 26(3):362--391, 1983.

Digital Library

[21]

Mikkel Thorup. Dynamic graph algorithms with applications. In 7th Scandinavian Workshop on Algorithm Theory, (SWAT), pages 1--9, 2000.

Digital Library

[22]

Mikkel Thorup. Fully-dynamic min-cut. Combinatorica, 27(1):91--127, 2007.

Digital Library

[23]

Zhengyu Wang. An improved randomized data structure for dynamic graph connectivity. CoRR, abs/1510.04590, 2015.

[24]

Christian Wulff-Nilsen. Faster deterministic fully-dynamic graph connectivity. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), pages 1757--1769, 2013.

Digital Library

[25]

Christian Wulff-Nilsen. Fully-dynamic minimum spanning forest with improved worst-case update time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, (STOC), pages 1130--1143, 2017.

Digital Library

Cited By

Luo MQin HWu XXiong CXia DKe Y(2024)Efficient Maintenance of Minimum Spanning Trees in Dynamic Weighted Undirected GraphsMathematics10.3390/math1207102112:7(1021)Online publication date: 28-Mar-2024
https://doi.org/10.3390/math12071021
Tseng TDhulipala LShun JAgrawal KLee I(2022)Parallel Batch-Dynamic Minimum Spanning Forest and the Efficiency of Dynamic Agglomerative Graph ClusteringProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538584(233-245)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1145/3490148.3538584
Acar UAnderson DBlelloch GDhulipala LScheideler CBerenbrink P(2019)Parallel Batch-Dynamic Graph ConnectivityThe 31st ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3323165.3323196(381-392)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1145/3323165.3323196

Index Terms

Improved Worst-Case Deterministic Parallel Dynamic Minimum Spanning Forest
1. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Dynamic graph algorithms
    2. Parallel algorithms

Recommendations

Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity

Deterministic fully dynamic graph algorithms are presented for connectivity, minimum spanning tree, 2-edge connectivity, and biconnectivity. Assuming that we start with no edges in a graph with n vertices, the amortized operation costs are O(log² n) for ...
Constant-time dynamic weight approximation for minimum spanning forest
Abstract
We give two fully dynamic algorithms that maintain a ( 1 + ε )-approximation of the weight M of a minimum spanning forest (MSF) of an n-node graph G with edges weights in [ 1 , W ], for any ε > 0. (1) Our deterministic algorithm takes ...
Fully-dynamic minimum spanning forest with improved worst-case update time
STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing

We give a Las Vegas data structure which maintains a minimum spanning forest in an n-vertex edge-weighted undirected dynamic graph undergoing updates consisting of any mixture of edge insertions and deletions. Each update is supported in O(n^{1/2 - c}) ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '18: Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures

July 2018

437 pages

ISBN:9781450357999

DOI:10.1145/3210377

General Chair:
Christian Scheideler
University of Paderborn, Germany
,
Program Chair:
Jeremy Fineman
Georgetown University, USA

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
EATCS: European Association for Theoretical Computer Science

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 July 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

SPAA '18

Sponsor:

SPAA '18: 30th ACM Symposium on Parallelism in Algorithms and Architectures

July 16 - 18, 2018

Vienna, Austria

Acceptance Rates

SPAA '18 Paper Acceptance Rate 36 of 120 submissions, 30%;

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
346
Total Downloads

Downloads (Last 12 months)69
Downloads (Last 6 weeks)15

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Luo MQin HWu XXiong CXia DKe Y(2024)Efficient Maintenance of Minimum Spanning Trees in Dynamic Weighted Undirected GraphsMathematics10.3390/math1207102112:7(1021)Online publication date: 28-Mar-2024
https://doi.org/10.3390/math12071021
Tseng TDhulipala LShun JAgrawal KLee I(2022)Parallel Batch-Dynamic Minimum Spanning Forest and the Efficiency of Dynamic Agglomerative Graph ClusteringProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538584(233-245)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1145/3490148.3538584
Acar UAnderson DBlelloch GDhulipala LScheideler CBerenbrink P(2019)Parallel Batch-Dynamic Graph ConnectivityThe 31st ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3323165.3323196(381-392)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1145/3323165.3323196

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents