论文标题
计算$ L（P，1）$ - 与组合参数的标签
Computing $L(p,1)$-Labeling with Combined Parameters
论文作者
论文摘要
给定图形，$ l（p，1）$ - 图形的标记是从顶点集到一组非负整数的分配$ f $，以便对于任何一对顶点$（u，v），| f（f（u） - f（u） - f（f（v）| \ ge p $如果$ u $和$ v $相邻，而$ f（u）\ neq f（v）$如果$ u $和$ v $在距离为$ 2 $。 $ l（p，1）$ - 标记问题是最小化$ f $的跨度（即$ \ max_ {u \ in v}（f（u）） - \ min_ {u \ in v}（f（u））+1 $）。众所周知，即使对于最高度$ 3 $的图形或带有树宽2的图形的图形也是NP-HARD，而相对于顶点盖号，它是固定参数可进行的。由于顶点覆盖号是一种最强的参数，因此从参数化的角度来看，障碍性和可行性之间存在很大的差距。为了填补差距，在本文中，我们提出了新的固定参数算法，以$ l（p，1）$ - 通过双盖号码加上最大集团大小的标签，并按照树的宽度和最高度。这些算法根据参数的几种组合减少了差距。
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)| \ge p$ if $u$ and $v$ are adjacent, and $f(u) \neq 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\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 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.
