On a labeling problem in graphs

R. Chandrasekaran, M. Dawande*, M. Baysan

*Bu çalışma için yazışmadan sorumlu yazar

Araştırma sonucu: Dergiye katkıMakalebilirkişi

Özet

Motivated by applications in software programming, we consider the problem of covering a graph by a feasible labeling. Given an undirected graph G=(V,E), two positive integers k and t, and an alphabet Σ, a feasible labeling is defined as an assignment of a set Lv⊆Σ to each vertex v∈V, such that (i) |Lv|≤k for all v∈V and (ii) each label α∈Σ is used no more than t times. An edge e=i,j is said to be covered by a feasible labeling if Li∩Lj≠Combining long solidus overlay. G is said to be covered if there exists a feasible labeling that covers each edge e∈E. In general, we show that the problem of deciding whether or not a tree can be covered is strongly NP-complete. For k=2, t=3, we characterize the trees that can be covered and provide a linear time algorithm for solving the decision problem. For fixed t, we present a strongly polynomial algorithm that solves the decision problem; if a tree can be covered, then a corresponding feasible labeling can be obtained in time polynomial in k and the size of the tree. For general graphs, we give a strongly polynomial algorithm to resolve the covering problem for k=2, t=3.

Orijinal dilİngilizce
Sayfa (başlangıç-bitiş)746-759
Sayfa sayısı14
DergiDiscrete Applied Mathematics
Hacim159
Basın numarası8
DOI'lar
Yayın durumuYayınlandı - 28 Nis 2011
Harici olarak yayınlandıEvet

Parmak izi

On a labeling problem in graphs' araştırma başlıklarına git. Birlikte benzersiz bir parmak izi oluştururlar.

Alıntı Yap