论文标题
永恒的顶点覆盖码最大外平图的数量
Eternal vertex cover number of maximal outerplanar graphs
论文作者
论文摘要
永恒的顶点覆盖问题是经典顶点盖问题的变体，该问题模型为两名玩家攻击者攻击者游戏。众所周知，计算永恒的顶点覆盖码通常是NP - hard，并且二分图的问题的复杂性状态是打开的。有一种二次复杂性算法以弦图而闻名。最大外平面图构成了弦图的子类，为此，没有算法的次级时间复杂性。在本文中，我们获得了线性时间的递归算法，用于计算永恒的顶点覆盖量最大外平面图的覆盖量。
Eternal vertex cover problem is a variant of the classical vertex cover problem modeled as a two player attacker-defender game. Computing eternal vertex cover number of graphs is known to be NP-hard in general and the complexity status of the problem for bipartite graphs is open. There is a quadratic complexity algorithm known for this problem for chordal graphs. Maximal outerplanar graphs forms a subclass of chordal graphs, for which no algorithm of sub-quadratic time complexity is known. In this paper, we obtain a recursive algorithm of linear time for computing eternal vertex cover number of maximal outerplanar graphs.
