论文部分内容阅读
最小边(点)排名问题是指如何使用最少的正整数给边(点)赋权值使得连接两个具有相同权值i的边(点)的任何一条路径上总存在一个权值大于i的边(点)。最小边排名问题在组装产品过程的并行组装调度方面有重要的应用。最小点排名问题则在正定矩阵的并行Cholesky分解、并行查询处理以及程序验证方面都有重要的应用。这两个问题在一般图上已经被证明是NP-hard的。在很多特殊图上(例如树、排列图和区间图等)的最小点排名问题却存在多项式时间的求解算法。与最小点排名问题相比,最小边排名问题的结论则相对较少,目前已知的是树、2-连通的外平面图和完全k-部图上的最小边排名问题具有多项式求解算法。
本文主要研究了特殊图上的最小边排名问题。具体地本文研究了树宽和度数均有界的图上的最小边排名问题,并给出了一个多项式时间求解算法。另外本文也从参数复杂性的角度考察了参数化的最小边排名问题的复杂性,给出了一个固定参数可解算法,从而说明参数化的最小边排名问题是固定参数可解的。
针对树宽和度数均有界的图上的最小边排名问题,本文将其转化为对应线图上的最小点排名问题并证明此时对应线图的树宽也是有界的,从而可以利用已有的树宽有界的图上的最小点排名问题的多项式时间求解算法,最终得到了原问题的一个多项式时间求解算法。
针对参数化的最小边排名问题,本文选择所求边排名的大小作为参数。通过证明若图的最小边排名有界那么图的度数和直径均有界,结合度数和直径问题具有Moore上界,本文得到了参数化最小边排名问题的一个核,并据此判定参数化的最小边排名问题是属于FPT类的。
本文最后对最小边排名问题的算法研究工作进行总结,并就进一步研究最小点排名问题和最小边排名问题给出了一些建议。