We study the complexity of the λ−L(p, q)-labelling problem for fixed λ, p, and q. The task is to assign vertices of a graph labels from the set {0, . . . , λ} such that labels of adjacent vertices differ by at least p while vertices with a common neighbor have different labels. We use two different reductions, one from the NAE-3SAT and the second one from the edge precoloring extension problem. 1
| Identifer | oai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:313738 |
| Date | January 2011 |
| Creators | Kupec, Martin |
| Contributors | Fiala, Jiří, Dvořák, Zdeněk |
| Source Sets | Czech ETDs |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/masterThesis |
| Rights | info:eu-repo/semantics/restrictedAccess |
Page generated in 0.0015 seconds