论文标题
用于计算仙人掌图的永恒顶点覆盖号的线性时间算法
A Linear Time Algorithm for Computing the Eternal Vertex Cover Number of Cactus Graphs
论文作者
论文摘要
永恒的顶点覆盖问题是经典顶点覆盖问题的动态变体。计算Eternal顶点覆盖量的图形是NP的障碍，并且该问题的已知算法结果很少。本文提出了一种用于计算仙人掌图的永恒顶点覆盖率的线性递归算法。与其他图形类别不同，对于永恒顶点覆盖率的多项式时间算法是基于直接从最小顶点覆盖的已知下限的有效计算性，我们表明它是某些子结构属性，可帮助有效地计算仙人掌图的永恒顶点。还介绍了每个块是边缘，一个循环或双连接弦图的结果的扩展。
The eternal vertex cover problem is a dynamic variant of the classical vertex cover problem. It is NP-hard to compute the eternal vertex cover number of graphs and known algorithmic results for the problem are very few. This paper presents a linear time recursive algorithm for computing the eternal vertex cover number of cactus graphs. Unlike other graph classes for which polynomial time algorithms for eternal vertex cover number are based on efficient computability of a known lower bound directly derived from minimum vertex cover, we show that it is a certain substructure property that helps the efficient computation of eternal vertex cover number of cactus graphs. An extension of the result to graphs in which each block is an edge, a cycle or a biconnected chordal graph is also presented.
