Near-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry-Breaking Problems

Shiri Antaki, Quanquan C. Liu, Shay Solomon

Type: Preprint

Publication Date: 2020-01-01

Citations: 0

DOI: https://doi.org/10.48550/arxiv.2010.16177

View

Locations

arXiv (Cornell University) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	Distributed Symmetry Breaking in Hypergraphs	2014	Shay Kutten Danupon Nanongkai Gopal Pandurangan Peter M. Robinson
+	Simple dynamic algorithms for Maximal Independent Set and other problems	2018	Manoj Gupta Shahbaz Khan
+ PDF Chat	Simple dynamic algorithms for Maximal Independent Set and other problems	2018	Manoj Gupta Shahbaz Khan
+	Simple dynamic algorithms for Maximal Independent Set and other problems	2018	Manoj Gupta Shahbaz Khan
+	Dynamic Distributed MIS with Improved Bounds.	2020	Shiri Antaki Quanquan C. Liu Shay Solomon
+	Fast and Simple Deterministic Algorithms for Highly-Dynamic Networks.	2019	Keren Censor-Hillel Neta Dafni Victor I. Kolobov Ami Paz Gregory Schwartzman
+ PDF Chat	Dynamic Maximal Matching in Clique Networks	2024	Minming Li Peter M. Robinson Xianbin Zhu
+	Fast Deterministic Algorithms for Highly-Dynamic Networks	2019	Keren Censor-Hillel Neta Dafni Victor I. Kolobov Ami Paz Gregory Schwartzman
+ PDF Chat	The Locality of Distributed Symmetry Breaking	2012	Leonid Barenboim Michael Elkin Seth Pettie Johannes Schneider
+ PDF Chat	Optimal Dynamic Distributed MIS	2016	Keren Censor-Hillel Elad Haramaty Zohar Karnin
+	Almost Optimal Distributed Algorithms for Large-Scale Graph Problems.	2015	Gopal Pandurangan Peter Robinson Michele Scquizzato
+	Average Awake Complexity of MIS and Matching	2023	Mohsen Ghaffari Julian Portmann
+	Deterministic Massively Parallel Symmetry Breaking for Sparse Graphs	2023	Jeff Giliberti Manuela Fischer Christoph Grunau
+	The Message Complexity of Distributed Graph Optimization	2023	Fabien Dufoulon Shreyas Pai Gopal Pandurangan Sriram V. Pemmaraju Peter Robinson
+ PDF Chat	Distributed Symmetry-Breaking Algorithms for Congested Cliques	2018	Leonid Barenboim V. B. Khazanov
+	Brief Announcement: Improved Distributed Approximations for Maximum-Weight Independent Set	2020	Ken‐ichi Kawarabayashi Seri Khoury Aaron Schild Gregory Schwartzman
+	Efficient Distributed Computation of MIS and Generalized MIS in Linear Hypergraphs	2018	Fabian Kühn Chaodong Zheng
+	Distributed Maximum Matching Verification in CONGEST	2020	Mohamad Ahmadi Fabian Kühn
+	Distributed Maximum Matching Verification in CONGEST	2020	Mohamad Ahmadi Fabian Kühn
+	Optimal Dynamic Distributed MIS	2015	Keren Censor-Hillel Elad Haramaty Zohar Karnin

Cited by (0)

Action	Title	Year	Authors

Citing (12)

Action	Title	Year	Authors
+	A fast and simple randomized parallel algorithm for the maximal independent set problem	1986	Noga Alon László Babai Alon Itai
+ PDF Chat	Simple deterministic algorithms for fully dynamic maximal matching	2013	Ofer Neiman Shay Solomon
+ PDF Chat	Optimal Dynamic Distributed MIS	2016	Keren Censor-Hillel Elad Haramaty Zohar Karnin
+	Simple dynamic algorithms for Maximal Independent Set and other problems	2018	Manoj Gupta Shahbaz Khan
+	Improved Algorithms for Fully Dynamic Maximal Independent Set	2018	Yuhao Du Hengjie Zhang
+ PDF Chat	Fully dynamic maximal independent set with sublinear update time	2018	Sepehr Assadi Krzysztof Onak Baruch Schieber Shay Solomon
+ PDF Chat	Local Distributed Algorithms in Highly Dynamic Networks	2019	Philipp Bamberger Fabian Kühn Yannic Maus
+ PDF Chat	Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time	2019	Shiri Chechik Tianyi Zhang
+ PDF Chat	Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time	2019	Soheil Behnezhad Mahsa Derakhshan MohammadTaghi Hajiaghayi Clifford Stein Madhu Sudan
+ PDF Chat	Derandomizing local distributed algorithms under bandwidth restrictions	2020	Keren Censor-Hillel Merav Parter Gregory Schwartzman
+ PDF Chat	Polylogarithmic-time deterministic network decomposition and distributed derandomization	2020	Václav Rozhoň Mohsen Ghaffari
+ PDF Chat	Improved Deterministic Network Decomposition	2021	Mohsen Ghaffari Christoph Grunau Václav Rozhoň