论文标题
使用距离监视图的边缘
Monitoring the edges of a graph using distances
论文作者
论文摘要
我们在网络监视领域引入了一个新的图理论概念。如果对于每个边缘$ e $ g $ of $ g $，则图$ g $的$ m $顶点是a \ emph {远程 - 边缘监控套装}，则有一个顶点$ x $ x $ $ m $和$ y $ y $ y $ g $的$ y $ g $，因此$ e $属于$ x $和$ x $和$ x $和y $之间的所有较短路径。我们用$ dem（g）$表示$ g $的最小尺寸。 $ m $的顶点表示由$ g $建模的网络中的距离探针；当边缘$ e $失败时，从$ x $到$ y $的距离增加，因此我们能够检测到失败。事实证明，我们不仅可以检测到它，而且我们甚至可以正确找到失败的边缘。 在本文中，我们启动了这一新概念的研究。我们表明，对于非平衡连接的图形$ g $的订单$ n $，$ 1 \ leq dem（g）\ leq n-1 $，$ dem（g）= 1 $，当时仅当$ g $是一棵树，而$ g $是一棵树，$ dem（g）= n-1 $，并且仅当它是完整的图形时。我们计算网格，超管和完整的两部分图的$ dem $的确切值。 然后，我们将$ dem $与其他标准图参数相关联。我们表明，$ demg）$受图表的树木的较低范围，并且由其顶点盖号码限制。它的反馈边缘设置数字也两倍也是上限。此外，我们用$ dem（g）= 2 $来表征连接的图形$ g $。 然后，我们表明，即使对于Apex图，确定输入图$ g $的$ dem（g）$也是一个NP完整问题。存在多项式时间对数因子近似算法，但是，即使对于小直径的两部分图和两块亚立方体图形，即使对于渐近上的近似值也是渐近的近似值，这是NP的差异。对于这种情况，当通过解决方案大小参数化时，问题也与固定参数不同。
We introduce a new graph-theoretic concept in the area of network monitoring. A set $M$ of vertices of a graph $G$ is a \emph{distance-edge-monitoring set} if for every edge $e$ of $G$, there is a vertex $x$ of $M$ and a vertex $y$ of $G$ such that $e$ belongs to all shortest paths between $x$ and $y$. We denote by $dem(G)$ the smallest size of such a set in $G$. The vertices of $M$ represent distance probes in a network modeled by $G$; when the edge $e$ fails, the distance from $x$ to $y$ increases, and thus we are able to detect the failure. It turns out that not only we can detect it, but we can even correctly locate the failing edge. In this paper, we initiate the study of this new concept. We show that for a nontrivial connected graph $G$ of order $n$, $1\leq dem(G)\leq n-1$ with $dem(G)=1$ if and only if $G$ is a tree, and $dem(G)=n-1$ if and only if it is a complete graph. We compute the exact value of $dem$ for grids, hypercubes, and complete bipartite graphs. Then, we relate $dem$ to other standard graph parameters. We show that $demG)$ is lower-bounded by the arboricity of the graph, and upper-bounded by its vertex cover number. It is also upper-bounded by twice its feedback edge set number. Moreover, we characterize connected graphs $G$ with $dem(G)=2$. Then, we show that determining $dem(G)$ for an input graph $G$ is an NP-complete problem, even for apex graphs. There exists a polynomial-time logarithmic-factor approximation algorithm, however it is NP-hard to compute an asymptotically better approximation, even for bipartite graphs of small diameter and for bipartite subcubic graphs. For such instances, the problem is also unlikey to be fixed parameter tractable when parameterized by the solution size.
