Linial for lists

DOI10.1007/S00446-022-00424-YOpenAlexW4280610780MaRDI QIDQ2104037FDOQ2104037

Authors: Yannic Maus, Tigran Tonoyan 

Publication date: 9 December 2022

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00446-022-00424-y

Recommendations

• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
• Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds
• Distributed \((\Delta+1)\)-coloring in linear (in \(\Delta\)) time
• Deterministic distributed vertex coloring in polylogarithmic time
• Distributed \(({\Delta}+1)\)-coloring in linear (in \({\Delta})\) time

zbMATH Keywords

list coloringcover-free familycolor reductiondeterministic distributed coloring

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Cites Work

• Distributed Computing: A Locality-Sensitive Approach
• Locality in Distributed Graph Algorithms
• Locality based graph coloring
• A fast distributed algorithm for \((\Delta+1)\)-edge-coloring
• A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
• Distributed (Δ +1)-Coloring in Sublogarithmic Rounds
• Distributed Graph Coloring: Fundamentals and Recent Developments
• On the complexity of distributed graph coloring
• Families of finite sets in which no set is covered by the union of \(r\) others
• Title not available (Why is that?)
• Local Computation
• On the complexity of distributed graph coloring with local minimality constraints
• The Locality of Distributed Symmetry Breaking
• Some simple distributed algorithms for sparse networks
• Deterministic Distributed Vertex Coloring in Polylogarithmic Time
• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
• Lower Bounds for Maximal Matchings and Maximal Independent Sets
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Deterministic distributed edge-coloring with fewer colors
• Truly Tight-in-Δ Bounds for Bipartite Maximal Matching and Variants
• Distributed $(\Delta+1)$-Coloring in Linear (in $\Delta$) Time
• Efficient Deterministic Distributed Coloring with Small Bandwidth
• Polynomial lower bound for distributed graph coloring in a weak LOCAL model
• Deterministic (Δ + 1)-Coloring in Sublinear (in Δ) Time in Static, Dynamic, and Faulty Networks
• Distributed Degree Splitting, Edge Coloring, and Orientations
• An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model
• On the complexity of local distributed graph problems
• Faster Deterministic Distributed Coloring Through Recursive List Coloring
• Locally-Iterative Distributed (Δ+ 1)
• An optimal distributed (Δ+1)-coloring algorithm?
• A lower bound for the distributed Lovász local lemma
• Locality of not-so-weak coloring
• Improved distributed degree splitting and edge coloring
• An Automatic Speedup Theorem for Distributed Problems
• Improved Distributed Delta-Coloring
• Towards the locality of Vizing’s theorem
• Distributed Edge Coloring in Time Quasi-Polylogarithmic in Delta
• Brief Announcement: Classification of Distributed Binary Labeling Problems
• Distributed Lower Bounds for Ruling Sets

Cited In (5)

• Lower bound for constant-size local certification
• Padded Lists Revisited
• Distributed coloring of hypergraphs
• Improved dynamic colouring of sparse graphs
• A representation for linear lists with movable fingers

This page was built for publication: Linial for lists

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2104037)