Neighborhood graphs and distributed Δ+1-coloring

DOI10.1007/3-540-61422-2_134zbMath1502.68235OpenAlexW1742880224MaRDI QIDQ5054815

Pierre Kelsen

Publication date: 9 December 2022

Published in: Algorithm Theory — SWAT'96 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-61422-2_134

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Randomized algorithms (68W20)

Related Items

Large cuts with local algorithms on triangle-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• Removing randomness in parallel computation without a processor penalty
• Deterministic coin tossing with applications to optimal parallel list ranking
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Complexity of network synchronization
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Parallel Symmetry-Breaking in Sparse Graphs
• Locality in Distributed Graph Algorithms
• What can be computed locally?
• Locality based graph coloring
• Fast randomized algorithms for distributed edge coloring