论文标题
仙人掌图的最低$ k $ hop统治集的线性时间算法
A Linear-Time Algorithm for Minimum $k$-Hop Dominating Set of a Cactus Graph
论文作者
论文摘要
给定图形$ g =（v，e）$和一个整数$ k \ ge 1 $，a $ k $ -hop占主导地位的$ d $ $ g $是$ v $的子集，因此，对于每个顶点$ v \ in v $ in v $，都存在于$ v $的d $中的节点$ u \ in v $ n of $ k $。 $ k $ -HOP主导的最低基数集被称为最低$ K $ -HOP主导套装。在本文中，我们提出了线性时间算法，这些算法在单车和仙人掌图中找到了最低$ K $ -HOP主导的占主导地位。为了实现这一目标，我们表明Unicycle图上的$ k $ domination设置问题还原为穿孔圆弧问题，并显示用于刺穿的圆形圆弧的线性时间算法，该算法改善了最著名的$ O（N \ log n \ log n）$ - 时间算法。
Given a graph $G=(V,E)$ and an integer $k \ge 1$, a $k$-hop dominating set $D$ of $G$ is a subset of $V$, such that, for every vertex $v \in V$, there exists a node $u \in D$ whose hop-distance from $v$ is at most $k$. A $k$-hop dominating set of minimum cardinality is called a minimum $k$-hop dominating set. In this paper, we present linear-time algorithms that find a minimum $k$-hop dominating set in unicyclic and cactus graphs. To achieve this, we show that the $k$-dominating set problem on unicycle graph reduces to the piercing circular arcs problem, and show a linear-time algorithm for piercing sorted circular arcs, which improves the best known $O(n\log n)$-time algorithm.
