arXiv preprint ·
Dynamic 3-Coloring of Bipartite Graphs with Optimal Locality
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We give a dynamic graph algorithm which maintains a 3-coloring in bipartite graphs under edge insertions such that the coloring only changes within a radius of $O(\log n)$ around an inserted edge. In the context of locality theory in distributed graph algorithms, this gives an upper bound on the locality under the dynamic-LOCAL model. Our bound on the locality is tight, as the problem admits a matching $Ω(\log n)$ lower bound in the stronger online-LOCAL model, by a result of Chang et al. [PODC 2024]. Thus, our result closes the gap between dynamic and online locality of this problem.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Scaling LLM Inference via Parallelism: Throughput-Latency Trade-off
Coordination-Free Workload Regularization for Variable-Cost Distributed Training
Beyond the Trial-and-Error Loop: Hybrid Projection and Automated Tuning for Distributed Training
HyCo: Hybrid Drafting for Cost-Efficient Mobile-Cloud Speculative Decoding
When the KV Cache Is Slower Than the GPU: Scaling Remote KV Tiers for Context-Parallel Prefill
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.