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.

Rights

URN

URN:NBN:SI:doc-YYI96HQV

COBISSID

14187097

Added

21.04.2016

Metadata

Citation

APA:

Fijavž, Gašper (2006). Coloring weighted series-parallel graphs. Informatica (Ljubljana), volume 30, issue 3, str. 321-324. URN:NBN:SI:doc-YYI96HQV from http://www.dlib.si

MLA:

Fijavž, Gašper. "Coloring weighted series-parallel graphs." Informatica (Ljubljana) volume 30. issue 3 (2006) str. 321-324.
<http://www.dlib.si/?URN=URN:NBN:SI:doc-YYI96HQV>

Informatica
1977-
(Assembly record)