Coloring weighted series-parallel graphs - Fijavž, Gašper (Informatica (Ljubljana), 2006)
Let ?$G$? be a series-parallel graph with integer edge weights. A ?$p$?-coloring of ?$G$? is a mapping of vertices of ?$G$? into ?$\ZZ_p$? (ring of integers modulo ?$p$?) so that the distance between colors of adjacent vertices of ?$u$? and ?$v$? is at least the weight of the edge ?$uv$?. We describe a quadratic time ?$p$?-coloring algorithm where ?$p$? is either twice the maximum edge weight or the largest possible sum of three weights of edges lying on a common cycle.
Keywords: matematika; mathematics; teorija grafov; uteženi grafi; barvanje grafov; algoritmi