A randomized algorithm for \(k\)-colorability

DOI10.1016/0012-365X(94)90402-2zbMath0805.05029OpenAlexW2159322473MaRDI QIDQ1331989

Janez Žerovnik

Publication date: 26 January 1995

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(94)90402-2

zbMATH Keywords

colouringrandomized algorithmcritical regions

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Clustering as a dual problem to colouring ⋮ Clustering via the modified Petford-Welsh algorithm ⋮ Unnamed Item ⋮ Unnamed Item

Cites Work

• Optimization by Simulated Annealing
• A randomised 3-colouring algorithm
• A parallel variant of a heuristical algorithm for graph coloring -- corrigendum
• A parallel variant of a heuristical algorithm for graph colouring
• A randomised heuristical algorithm for estimating the chromatic number of a graph
• Almost all k-colorable graphs are easy to color

This page was built for publication: A randomized algorithm for \(k\)-colorability