Computing L(p,1)-Labeling with Combined Parameters
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 and v, |f (u) - f (v)| p if u and v are adjacent, and f(u) eq 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.,_uV(f(u)) - _uV(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 the 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. , number=2, journal=Journal of Graph Algorithms and Applications, author=Hanaka, Tesshu and Kawai, Kazuma and Ono, Hirotaka, year=2022, month=Jun., pages=241–255