Answers are grounded in this paper and cite their sources.
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) ≠ 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.,maxu∈ V(f(u)) - minu∈ 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)- L 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.
No takes yet. Share an insight, caveat, or question.
Hanaka et al. (2022) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: