Performance ratio of the generalized greedy algorithm for q-coloring problem

zbMATH Open1347.68350MaRDI QIDQ2826435FDOQ2826435

Authors: R. O. Adamyan 

Publication date: 17 October 2016

Published in: Uchenye Zapiski Erevanskogo Gosudarstvennogo Universiteta. Estestvennye Nauki (Search for Journal in Brave)

Full work available at URL: http://www.ysu.am/files/Inf.pdf

Recommendations

• An on-line graph coloring algorithm with sublinear performance ratio
• Improving the performance guarantee for approximate graph coloring
• The greedy algorithm is optimal for on-line edge coloring
• scientific article; zbMATH DE number 5859
• The greedy coloring is a bad probabilistic algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Nonnumerical algorithms (68W05) Coloring of graphs and hypergraphs (05C15)

This page was built for publication: Performance ratio of the generalized greedy algorithm for \(q\)-coloring problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2826435)