Copertina

A Tight Lower Bound for 3-Coloring Grids in the Online-LOCAL Model

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Chang, Yi-Jun, Mishra, Gopinath, Nguyen, Hung Thuan, Yang, Mingyang, Yeh, Yu-Cheng
Natura:	Preprint
Pubblicazione:	2023
Soggetti:	Data Structures and Algorithms Distributed, Parallel, and Cluster Computing
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Round and Communication Efficient Graph Coloring
di: Chang, Yi-Jun, et al.
Pubblicazione: (2024)

Optimal Distributed Replacement Paths
di: Chang, Yi-Jun, et al.
Pubblicazione: (2025)

Overlay Network Construction: Improved Overall and Node-Wise Message Complexity
di: Chang, Yi-Jun, et al.
Pubblicazione: (2024)

Narrowing the LOCAL$\unicode{x2013}$CONGEST Gaps in Sparse Networks via Expander Decompositions
di: Chang, Yi-Jun, et al.
Pubblicazione: (2022)

Tight Bounds on the Message Complexity of Distributed Tree Verification
di: Kutten, Shay, et al.
Pubblicazione: (2024)

Low-Distortion Clustering in Bounded Growth Graphs
di: Chang, Yi-Jun, et al.
Pubblicazione: (2024)

Tight Bounds for Constant-Round Domination on Graphs of High Girth and Low Expansion
di: Lenzen, Christoph, et al.
Pubblicazione: (2024)

Bounded Memory in Distributed Networks
di: Basat, Ran Ben, et al.
Pubblicazione: (2025)

Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications
di: Chang, Yi-Jun
Pubblicazione: (2023)

Deterministic Lower Bounds for $k$-Edge Connectivity in the Distributed Sketching Model
di: Robinson, Peter, et al.
Pubblicazione: (2025)

Energy-Efficient Aggregation and Minimum-Degree Spanning Trees in Radio Networks
di: Chang, Yi-Jun, et al.
Pubblicazione: (2026)

Optimal local certification on graphs of bounded pathwidth
di: Baterisna, Dan Alden, et al.
Pubblicazione: (2025)

Deterministic Expander Routing: Faster and More Versatile
di: Chang, Yi-Jun, et al.
Pubblicazione: (2024)

Universally Optimal Information Dissemination and Shortest Paths in the HYBRID Distributed Model
di: Chang, Yi-Jun, et al.
Pubblicazione: (2023)

Memory Bounds for Concurrent Bounded Queues
di: Aksenov, Vitaly, et al.
Pubblicazione: (2021)

Fast Broadcast in Highly Connected Networks
di: Chandra, Shashwat, et al.
Pubblicazione: (2024)

Improved All-Pairs Approximate Shortest Paths in Congested Clique
di: Bui, Hong Duc, et al.
Pubblicazione: (2024)

Orientation does not help with 3-coloring a grid in online-LOCAL
di: Boudier, Thomas, et al.
Pubblicazione: (2025)

Towards Optimal Distributed Edge Coloring with Fewer Colors
di: Jakob, Manuel, et al.
Pubblicazione: (2025)

Sublogarithmic Distributed Vertex Coloring with Optimal Number of Colors
di: Flin, Maxime, et al.
Pubblicazione: (2026)

Decentralized Distributed Graph Coloring II: degree+1-Coloring Virtual Graphs
di: Flin, Maxime, et al.
Pubblicazione: (2024)

Theoretical Lower Bounds for the Oven Scheduling Problem
di: Da Ros, Francesca, et al.
Pubblicazione: (2024)

Towards Optimal Distributed Delta Coloring
di: Jakob, Manuel, et al.
Pubblicazione: (2025)

Competitive Capacitated Online Recoloring
di: Rajaraman, Rajmohan, et al.
Pubblicazione: (2024)

Adaptive Massively Parallel Coloring in Sparse Graphs
di: Latypov, Rustam, et al.
Pubblicazione: (2024)

Distributed Delta-Coloring under Bandwidth Limitations
di: Maus, Yannic, et al.
Pubblicazione: (2024)

Faster Distributed $Δ$-Coloring via Ruling Subgraphs
di: Bourreau, Yann, et al.
Pubblicazione: (2025)

Improved Approximation Bounds for Minimum Weight Cycle in the CONGEST Model
di: Manoharan, Vignesh, et al.
Pubblicazione: (2023)

Faster Distributed $Δ$-Coloring via a Reduction to MIS
di: Bourreau, Yann, et al.
Pubblicazione: (2025)

Near Optimal Bounds for Replacement Paths and Related Problems in the CONGEST Model
di: Manoharan, Vignesh, et al.
Pubblicazione: (2022)

Online Load and Graph Balancing for Random Order Inputs
di: Im, Sungjin, et al.
Pubblicazione: (2024)

Multi-Agent Online Graph Exploration on Cycles and Tadpole Graphs
di: Akker, Erik van den, et al.
Pubblicazione: (2024)

Parallel Batch Dynamic Vertex Coloring in $O(\log Δ)$ Amortized Update Time
di: Hutton, Chase, et al.
Pubblicazione: (2025)

The Online Pause and Resume Problem: Optimal Algorithms and An Application to Carbon-Aware Load Shifting
di: Lechowicz, Adam, et al.
Pubblicazione: (2023)

Asynchronous Collective Tree Exploration: a Distributed Algorithm, and a new Lower Bound
di: Cosson, Romain, et al.
Pubblicazione: (2025)

A Scalable and Unified Framework to Weighted Rank Aggregation
di: Carmel, Amir, et al.
Pubblicazione: (2026)

Zarr-Based Chunk-Level Cumulative Sums in Reduced Dimensions
di: Zhang, Hailiang, et al.
Pubblicazione: (2025)

Efficient Enumeration of Large Maximal k-Plexes
di: Cheng, Qihao, et al.
Pubblicazione: (2024)

Evaluation of Dynamic Vector Bin Packing for Virtual Machine Placement
di: Lee, Zong Yu, et al.
Pubblicazione: (2026)

Efficient Dynamic MaxFlow Computation on GPUs
di: Kannappan, Shruthi, et al.
Pubblicazione: (2025)