A randomised heuristical algorithm for estimating the chromatic number of a graph

DOI10.1016/0020-0190(89)90144-0zbMath0686.68058OpenAlexW2121434721MaRDI QIDQ1262784

Janez Žerovnik

Publication date: 1989

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90144-0

zbMATH Keywords

combinatorial problemgraph colouringrandomised heuristicsantivoter algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Algorithms in computer science (68W99)

Related Items (1)

A randomized algorithm for \(k\)-colorability

Cites Work

• Optimization by Simulated Annealing
• Finite particle systems and infection models
• Computational Complexity of Probabilistic Turing Machines
• An upper bound for the chromatic number of a graph and its application to timetabling problems
• Unnamed Item
• Unnamed Item

This page was built for publication: A randomised heuristical algorithm for estimating the chromatic number of a graph