VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
• On semidefinite programming based heuristics for the graph coloring problem
Đukanović, Igor, matematik ...
The Lovász theta number is a well-known lower bound on the chromatic number of a graph $G$. and $\Psi_K(G)$is its impressive strengthening. We apply semidefinite programming formulation of a both ... functions to obtain suboptimal (matrix) solutions in a polynomial time. These matrices carry valuable information on how to color the graph. The resulting graph coloring heuristics utilizing these two functions are compared on medium sized graphs.
Vir: SOR '11 proceedings (Str. 103-108)
Vrsta gradiva - prispevek na konferenci
Leto - 2011
Jezik - angleški
COBISS.SI-ID - 16048217
vir: SOR '11 proceedings (Str. 103-108)