Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring

DOI10.1007/s00446-016-0269-8zbMath1408.68131arXiv1601.04306OpenAlexW2594917573MaRDI QIDQ518926

Lei Xu, Alexander D. Scott, Peter G. Jeavons

Publication date: 4 April 2017

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

Full work available at URL: https://arxiv.org/abs/1601.04306

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (4)

Design patterns in beeping algorithms: examples, emulation, and analysis ⋮ Computing large independent sets in a single round ⋮ Distributed Self-Stabilizing MIS with Few States and Weak Communication ⋮ Noisy beeping networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithms for some graph problems on a distributed computational model
• An optimal bit complexity randomized distributed MIS algorithm
• About randomised distributed graph colouring and graph partition algorithms
• Symmetry breaking in distributed networks
• Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
• Linear time self-stabilizing colorings
• Legal coloring of graphs
• Graph coloring on coarse grained multicomputers
• Simple distributed \(\Delta+1\)-coloring of graphs
• Patterns from nature: distributed greedy colouring with simple messages and minimal graph knowledge
• Beeping a maximal independent set
• Linear degree extractors and the inapproximability of max clique and chromatic number
• A log-star distributed maximal independent set algorithm for growth-bounded graphs
• On the complexity of distributed graph coloring with local minimality constraints
• A Biological Solution to a Fundamental Distributed Computing Problem
• Local Computation
• The Locality of Distributed Symmetry Breaking
• Knowledge and common knowledge in a distributed environment
• The price of being near-sighted
• Deploying Wireless Networks with Beeps
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A fast parallel algorithm for the maximal independent set problem
• Parallel Symmetry-Breaking in Sparse Graphs
• Locality in Distributed Graph Algorithms
• Distributed Computing: A Locality-Sensitive Approach
• On the Complexity of Distributed Network Decomposition
• Reducibility among Combinatorial Problems
• Some simple distributed algorithms for sparse networks
• Distributed (δ+1)-coloring in linear (in δ) time
• Stone age distributed computing
• Feedback from nature
• A new technique for distributed symmetry breaking
• Maximal independent sets in radio networks
• On the complexity of distributed graph coloring
• APPLICATION OF THE GRAPH COLORING ALGORITHM TO THE FREQUENCY ASSIGNMENT PROBLEM
• Euro-Par 2004 Parallel Processing
• Simple Neural-Like P Systems for Maximal Independent Set Selection
• Distributed Computing
• Deterministic Distributed Vertex Coloring in Polylogarithmic Time
• What cannot be computed locally!

This page was built for publication: Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring