On a labeling problem in graphs

作     者：Chandrasekaran, R. Dawande, M. Baysan, M. 

作者机构：Univ Texas Dallas Sch Management Richardson TX 75083 USA Univ Texas Dallas Dept Comp Sci Richardson TX 75083 USA Univ Toronto Dept Comp Sci Toronto ON M5S 1A1 Canada 

出 版 物：《DISCRETE APPLIED MATHEMATICS》 (离散应用数学)

年 卷 期：2011年第159卷第8期

页      面：746-759页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：Graph algorithms Software programming Complexity 

摘      要：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 E, a feasible labeling is defined as an assignment of a set L c to each vertex v is an element of V. such that (i) vertical bar L-v vertical bar = k for all v is an element of V and (ii) each label a is an element of Sigma is used no more than t times. An edge e = {i, j} is said to be covered by a feasible labeling L-i boolean AND L-j not equal empty set. G is said to be covered if there exists a feasible labeling that covers each edge e 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. (C) 2011 Elsevier B.V. All rights reserved.