کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649874 | 1342468 | 2009 | 12 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Perfectness and imperfectness of unit disk graphs on triangular lattice points Perfectness and imperfectness of unit disk graphs on triangular lattice points](/preview/png/4649874.png)
Given a finite set of 2-dimensional points P⊆R2P⊆R2 and a positive real dd, a unit disk graph, denoted by (P,d)(P,d), is an undirected graph with vertex set PP such that two vertices are adjacent if and only if the Euclidean distance between the pair is less than or equal to dd. Given a pair of non-negative integers mm and nn, P(m,n)P(m,n) denotes a subset of 2-dimensional triangular lattice points defined by P(m,n)=def.{(xe1+ye2)∣x∈{0,1,…,m−1},y∈{0,1,…,n−1}} where e1=def.(1,0),e2=def.(1/2,3/2). Let Tm,n(d)Tm,n(d) be a unit disk graph defined on a vertex set P(m,n)P(m,n) and a positive real dd. Let Tm,nk be the kkth power of Tm,n(1)Tm,n(1).In this paper, we show necessary and sufficient conditions that [∀m,Tm,n(d) is perfect] and/or [∀m,Tm,nk is perfect], respectively. These conditions imply polynomial time approximation algorithms for multicoloring (Tm,n(d),w)(Tm,n(d),w) and (Tm,nk,w).
Journal: Discrete Mathematics - Volume 309, Issue 9, 6 May 2009, Pages 2733–2744