单圈图的点覆盖k-路问题的有效算法

利用贪婪算法的思想,给出了一个求解树上点覆盖k-路问题的有效算法,并且进一步针对单圈图的点覆盖k-路问题,给出了一个能在多项式时间内完成的有效算法。

k路覆盖图的新充分条件（英文）

设G是一个n阶简单连通图。如果其顶点集V (G)能被k条或更少的点不交的路覆盖,则图G是k-路覆盖的。分别用距离谱半径、距离无符号拉普拉斯谱半径、Wiener指数和Harary指数得到了图G是k-路覆盖的新的充分条件。

Series-Parallel图上最小权顶点覆盖3-路问题的有效算法

研究了Series-Parallel图上的顶点覆盖3-路问题,利用动态规划思想,给出一个能在多项式时间内完成的有效算法,该算法的运行时间为O(|V|)。

星图与二部图的某些乘积图上的k-路点覆盖

对于一个点子集S■V(G),如果图G中任意一条k路上都有至少一个点来自于S,则称集合S是图G的一个k-路点覆盖。最小的k-路点覆盖集合的阶数为图G的k-路点覆盖数,记作ψ_(k)(G)。研究了星图与二部图的笛卡尔乘积图、字典积图和直乘积图上的k-路点覆盖问题,运用枚举法以及子图的相关概念,得到了它们的最小k-路点覆盖ψ_(k)(G)值的上、下界。

笛卡尔乘积图的k-路点覆盖

对于一个图G和一个正整数k,若图G中任意一条阶数为k的路都至少包含集合S?V(G)中的一个顶点,那么集合S就为图G的一个k-路点覆盖。最小的k-路点覆盖基数记为ψk(G),为图G的k-路点覆盖数。研究圈图分别与圈图、完全图及完全二部图做笛卡尔乘积图的k-路点覆盖,得到ψk(G)相关的精确值和上下界。