论文标题
在单位磁盘图上施泰纳树的参数化研究
Parameterized Study of Steiner Tree on Unit Disk Graphs
论文作者
论文摘要
我们研究了单位磁盘图上的施泰纳树问题。给定$ n $顶点单元磁盘图$ g $，一个子集$ r \ subseteq v（g）$ $ t $ vertices和一个正整数$ k $，目的是确定是否存在$ r $的所有$ r $的$ r $的$ g $中的树$ t $ in $ r $，并且最多使用$ k $ vertices in $ k $ v n $ v $ v $ n $ r $ r $ r $ r $ r $ r $ r $ r $ r $ r \ r $ r \ r r $ r $ r。 $ r $的顶点称为终端，$ v（g）\ setminus r $作为steiner顶点的顶点。首先，我们表明问题是NP-HARD。接下来，我们证明可以在$ n^{o（\ sqrt {t+k}）} $ time中求解单位磁盘图上的施泰纳树问题。我们还表明，由$ k $参数化的单位磁盘图上的施泰纳树问题具有fpt算法，运行时间$ 2^{o（k）} n^{o（1）} $。实际上，该算法是为更通用的图表设计的，称为Clique-Grid图。我们提到的是，可以在磁盘图上使用有界纵横比的磁盘图上的算法结果。最后，我们证明了由$ k $参数化的磁盘图上的施泰纳树是[1] -hard。
We study the Steiner Tree problem on unit disk graphs. Given a $n$ vertex unit disk graph $G$, a subset $R\subseteq V(G)$ of $t$ vertices and a positive integer $k$, the objective is to decide if there exists a tree $T$ in $G$ that spans over all vertices of $R$ and uses at most $k$ vertices from $V\setminus R$. The vertices of $R$ are referred to as terminals and the vertices of $V(G)\setminus R$ as Steiner vertices. First, we show that the problem is NP-Hard. Next, we prove that the Steiner Tree problem on unit disk graphs can be solved in $n^{O(\sqrt{t+k})}$ time. We also show that the Steiner Tree problem on unit disk graphs parameterized by $k$ has an FPT algorithm with running time $2^{O(k)}n^{O(1)}$. In fact, the algorithms are designed for a more general class of graphs, called clique-grid graphs. We mention that the algorithmic results can be made to work for the Steiner Tree on disk graphs with bounded aspect ratio. Finally, we prove that the Steiner Tree on disk graphs parameterized by $k$ is W[1]-hard.
