Home  Issues  About JGAA  Instructions for Authors 
Special Issue on Selected Papers from the 15th International Conference and Workshops on Algorithms and Computation, WALCOM 2021
DOI: 10.7155/jgaa.00592
Computing L(p,1)Labeling with Combined Parameters
Tesshu Hanaka,
Kazuma Kawai, and
Hirotaka Ono
Vol. 26, no. 2, pp. 241255, 2022. Regular paper.
Abstract 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) \ge p$ if $u$ and $v$ are adjacent, and $f(u) \neq f(v)$ if $u$ and $v$ are at distance $2$. The \textsc{$L(p,1)$labeling} problem is to minimize the span of $f$ (i.e.,$\max_{u\in V}(f(u))  \min_{u\in V}(f(u))+1$).
It is known to be NPhard even for graphs of maximum degree $3$ or graphs with treewidth 2, whereas it is fixedparameter 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 fixedparameter algorithms for ${L(p,1){\rm L{\small ABELING}}}$ by the twin cover number plus the maximum clique size and by the treewidth plus the maximum degree. These algorithms reduce the gap in terms of several combinations of parameters.
This work is licensed under the terms of the CCBY license.

Submitted: March 2021.
Reviewed: October 2021.
Accepted: December 2021.
Final: December 2021.
Revised: December 2021.
Published: June 2022.

Journal Supporters
