Special Issue on Selected Papers from the 15th International Conference and Workshops on Algorithms and Computation, WALCOM 2021 Computing L(p,1)-Labeling with Combined Parameters Tesshu Hanaka, Kazuma Kawai, and Hirotaka Ono Vol. 26, no. 2, pp. 241-255, 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 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)-{\rm L{\small ABELING}}}$ 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.  This work is licensed under the terms of the CC-BY license. Submitted: March 2021. Reviewed: October 2021. Accepted: December 2021. Final: December 2021. Revised: December 2021. Published: June 2022. Communicated by Seok-Hee Hong, Subhas C. Nandy, and Ryuhei Uehara article (PDF) BibTeX