TY - JOUR
T1 - On a labeling problem in graphs
AU - Chandrasekaran, R.
AU - Dawande, M.
AU - Baysan, M.
PY - 2011/4/28
Y1 - 2011/4/28
N2 - 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.
AB - 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.
KW - Complexity
KW - Graph algorithms
KW - Software programming
UR - http://www.scopus.com/inward/record.url?scp=79952532333&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2010.12.022
DO - 10.1016/j.dam.2010.12.022
M3 - Article
AN - SCOPUS:79952532333
SN - 0166-218X
VL - 159
SP - 746
EP - 759
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
IS - 8
ER -