Patterns from nature: distributed greedy colouring with simple messages and minimal graph knowledge

DOI10.1016/j.ins.2014.06.035zbMath1390.90453OpenAlexW2057824797WikidataQ114826625 ScholiaQ114826625MaRDI QIDQ1749842

Lei Xu, Peter G. Jeavons

Publication date: 17 May 2018

Published in: Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ins.2014.06.035

zbMATH Keywords

distributed computingrandomised algorithmbio-inspired algorithmgreedy colouring

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Approximation methods and heuristics in mathematical programming (90C59) Coloring of graphs and hypergraphs (05C15) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20)

Related Items (3)

Efficient pattern matching on big uncertain graphs ⋮ Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring ⋮ On the Microscopic View of Time and Messages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithms for some graph problems on a distributed computational model
• Linear time self-stabilizing colorings
• Legal coloring of graphs
• Graph coloring on coarse grained multicomputers
• Simple distributed \(\Delta+1\)-coloring of graphs
• An experimental analysis of simple, distributed vertex coloring algorithms
• Beeping a maximal independent set
• An ant-based algorithm for coloring graphs
• Linear degree extractors and the inapproximability of max clique and chromatic number
• On the complexity of distributed graph coloring with local minimality constraints
• A Biological Solution to a Fundamental Distributed Computing Problem
• Deploying Wireless Networks with Beeps
• Locality in Distributed Graph Algorithms
• On colouring random graphs
• Some simple distributed algorithms for sparse networks
• Feedback from nature
• APPLICATION OF THE GRAPH COLORING ALGORITHM TO THE FREQUENCY ASSIGNMENT PROBLEM
• Euro-Par 2004 Parallel Processing

This page was built for publication: Patterns from nature: distributed greedy colouring with simple messages and minimal graph knowledge