کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419469 | 683818 | 2011 | 11 صفحه PDF | دانلود رایگان |
The L(2,1)L(2,1)-labeling problem consists of assigning colors from the integer set 0,…,λ0,…,λ to the nodes of a graph GG in such a way that nodes at a distance of at most two get different colors, while adjacent nodes get colors which are at least two apart. The aim of this problem is to minimize λλ and it is in general NP-complete. In this paper the problem of L(2,1)L(2,1)-labeling unigraphs, i.e. graphs uniquely determined by their own degree sequence up to isomorphism, is addressed and a 3/23/2-approximate algorithm for L(2,1)L(2,1)-labeling unigraphs is designed. This algorithm runs in O(n)O(n) time, improving the time of the algorithm based on the greedy technique, requiring O(m)O(m) time, that may be near to Θ(n2)Θ(n2) for unigraphs.
Journal: Discrete Applied Mathematics - Volume 159, Issue 12, 28 July 2011, Pages 1196–1206