Fetching the paper…
Reading the bibliography…
In recent years, there has been a growing interest in solving various graph coloring problems in the streaming model.
Universal classes of hash functions
Larry Carter and Mark N. Wegman · 1979
Earlier work this paper cites.
Register allocation & spilling via graph coloring
Gregory J. Chaitin · 1982
Earlier work this paper cites.
A graph coloring algorithm for large scale scheduling problems
Vahid Lotfi and Sanjiv Sarin · 1986
Earlier work this paper cites.
Coloring away communication in parallel query optimization
Waqar Hasan and Rajeev Motwani · 1995
Earlier work this paper cites.
A new technique for distributed symmetry breaking
Johannes Schneider and Roger Wattenhofer · 2010
Earlier work this paper cites.
Vcolor: A practical vertex-cut based approach for coloring large graphs
Yun Peng, Byron Choi, Bingsheng He, Shuigeng Zhou, Ruzhi Xu, and Xiaohui Yu · 2016
Earlier work this paper cites.
Dynamic algorithms for graph coloring
Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger, and Danupon Nanongkai · 2018
Earlier work this paper cites.
Suman Kalyan Bera and Prantar Ghosh · 2018
Earlier work this paper cites.
An optimal distributed ( Δ \Delta +1)-coloring algorithm?
Yi-Jun Chang, Wenzheng Li, and Seth Pettie · 2018
Earlier work this paper cites.
Sublinear algorithms for ( Δ \Delta + 1) vertex coloring
Sepehr Assadi, Yu Chen, and Sanjeev Khanna · 2019
Earlier work this paper cites.
Smaller cuts, higher lower bounds
Amir Abboud, Keren Censor-Hillel, Seri Khoury, and Ami Paz · 2019
Earlier work this paper cites.
Independent sets in vertex-arrival streams
Graham Cormode, Jacques Dark, and Christian Konrad · 2019
Cited alongside, same era.
Palette sparsification beyond ( Δ \Delta +1) vertex coloring
Noga Alon and Sepehr Assadi · 2020
Cited alongside, same era.
Graph coloring via degeneracy in streaming and other space-conscious models
Suman K. Bera, Amit Chakrabarti, and Prantar Ghosh · 2020
Cited alongside, same era.
A framework for adversarially robust streaming algorithms
Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, and Eylon Yogev · 2020
Cited alongside, same era.
Efficient deterministic distributed coloring with small bandwidth
Philipp Bamberger, Fabian Kuhn, and Yannic Maus · 2020
Cited alongside, same era.
The adversarial robustness of sampling
Omri Ben-Eliezer and Eylon Yogev · 2020
Cited alongside, same era.
Adversarial robustness of streaming algorithms through importance sampling
Vladimir Braverman, Avinatan Hassidim, Yossi Matias, Mariano Schain, Sandeep Silwal, and Samson Zhou · 2021
Later among the works it cites.
Deterministic distributed vertex coloring: Simpler, faster, and without network decomposition
Mohsen Ghaffari and Fabian Kuhn · 2021
Later among the works it cites.
Separating adaptive streaming from oblivious streaming using the bounded storage model
Haim Kaplan, Yishay Mansour, Kobbi Nissim, and Uri Stemmer · 2021
Later among the works it cites.
Tight bounds for adversarially robust streams and sliding windows via difference estimators
David P. Woodruff and Samson Zhou · 2021
Later among the works it cites.
Deterministic graph coloring in the streaming model
Sepehr Assadi, Andrew Chen, and Glenn Sun · 2022
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Adversarially robust streaming algorithms via differential privacy
Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer · 2020
Cited alongside, same era.
Faster deterministic distributed coloring through recursive list coloring
Fabian Kuhn · 2020
Cited alongside, same era.
A framework for adversarial streaming via differential privacy and difference estimators
Idan Attias, Edith Cohen, Moshe Shechner, and Uri Stemmer · 2021
Cited alongside, same era.
Even the easiest(?) graph coloring problem is not easy in streaming!
Anup Bhattacharya, Arijit Bishnu, Gopinath Mishra, and Anannya Upasana · 2021
Cited alongside, same era.
Adversarially robust streaming via dense–sparse trade-offs
Omri Ben-Eliezer, Talya Eden, and Krzysztof Onak · 2021
Cited alongside, same era.
Brooks’ theorem in graph streams: a single-pass semi-streaming algorithm for Δ \Delta -coloring
Sepehr Assadi, Pankaj Kumar, and Parth Mittal · 2022
Closest in time.
Adversarially robust coloring for graph streams
Amit Chakrabarti, Prantar Ghosh, and Manuel Stoeckl · 2022
Closest in time.
On the robustness of countsketch to adaptive inputs
Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Moshe Shechner, and Uri Stemmer · 2022
Closest in time.
Near-optimal distributed degree+1 coloring
Magnus M. Halldorsson, Fabian Kuhn, Alexandre Nolin, and Tigran Tonayan · 2022
Closest in time.
Streaming algorithms for the missing item finding problem
Manuel Stoeckl · 2023
Closest in time.