Computing L(p,1)-Labeling with Combined Parameters
share
Given a graph, an L(p,1)-labeling of the graph is an assignment f from the vertex set to the set of nonnegative integers such that for any pair of vertices (u,v),|f (u) - f (v)| ≥ p if u and v are adjacent, and f(u) ≠ f(v) if u and v are at distance 2. The L(p,1)-labeling problem is to minimize the span of f (i.e.,max_u∈ V(f(u)) - min_u∈ V(f(u))+1). It is known to be NP-hard even for graphs of maximum degree 3 or graphs with tree-width 2, whereas it is fixed-parameter tractable with respect to vertex cover number. Since vertex cover number is a kind of the strongest parameter, there is a large gap between tractability and intractability from the viewpoint of parameterization. To fill up the gap, in this paper, we propose new fixed-parameter algorithms for L(p,1)-Labeling by the twin cover number plus the maximum clique size and by the tree-width plus the maximum degree. These algorithms reduce the gap in terms of several combinations of parameters.
READ FULL TEXT