一般图的不交路划分问题

给定一个阶为n的简单图G=(V;E),其中α(G)≥4,及1个正整数k≥2,考虑在领域条件下G划分成k条点不交路的问题,并得到下面的结果:对G中任何4个独立点x1,x2,y1,y2,满足领域条件,｜NG(x1)∪NG(x2)｜+｜NG(y1)∪NG(y2)｜≥n-k-1,则要么G能划分成k条点不交的路,要么G属于一类例外图G′.

边赋权森林ω-路划分的O(n)算法

w-路划分问题是路划分问题的一般化,它源于并行计算机系统、计算机网络与分布式控制系统等一类广播通信问题.设置最少的信息源节点,使得在指定的时间内将信息源节点所拥有的信息发送到其余节点,并且保证不同通信线路之间不得相交.从Hamilton路的NP-完全性不难看出,w-路划分问题属于NP-完全问题.通过构造性证明技术,获得了边赋非负权路径、树和森林的w-路划分问题的一些性质.分别提出了求解边赋非负权路径和边赋非负权树的w-路划分问题的线性时间算法,讨论了算法的局部实现技术,详细地分析了这些算法的复杂度.以这两个算法为基础,提出了一个线性时间算法求解边赋非负权森林的w-路划分问题.所提出的算法直观简明、操作容易,只需要较少的运行时间和较小的存储空间.