本站原创论文摘 要 : 最小边(点)排名问题是指如何使用最少的正整数给边(点)赋权值使得连接两个具有相同（略）点)的任何一条路径上总存在一个权值大于i的边(点).最小边排名问题在组装产品过程的并行组装调度方面有重要的应用.最小点排名问题则在正定矩阵的并行（略）ky分解、并行查询处理以及程序验证方面都有重要的应用.这两个问题在一般图上已经被证明是NP-hard的.在很多特殊图上(例如树、排列图和区间图等（略）名问题却存在多项式时间的求解算法.与最小点排名问题相比,最小边排名问题的结论则相对较少,目前已知的是树、2-连通的外平面图和完全k-部图上的最小边排名问题具有多项式求解算法. 本文主要研究了特殊图上的最小边排名问题.具体地本文研究了树宽和度数均有界的图上的最小（略）并给出了一个多项式时间求解算法.另外本文也从参数复杂性的角度考察了参数化的最小边排名问题的复杂性,给出了一个固定参数可解算法,从而说明参数化的最小边排（略）参数可解的. 针对树宽和度数均有界的图上的最小边排名问题,本文将其转化为对应线图上的最小点排名问题并证明此时对应线图的树宽也是有界的,从而可以利用已有的树宽有界...The minimum edge （omitted）ankin（omitted）is to find a weight assignment of the edges (vertices) of the input graph with leas（omitted）f integers such that every path connecting two edges (vertices) with the same weight i contains an intermediat（omitted）rtex) with weight greater than i. The minimum edge ranking problem has application in scheduling of parallel assembly of a product from its ponents while（omitted）um vertex ranking problem plays an important role in puting Cholesky factorization...目录:摘 要第4-5页 Abstract 第5-6页 第1章 引言 第8-12页 ·,课题的研究背景和意义 第9-10页 ·,课题的研究内容 第10-11页 ·,论文组织 第11-12页 第2章 相关研究工作 第12-25页 ·,本文用到的一些术语 第12-15页 ·,图论的基本概念 第12-14页 ·,参数复杂性理论简介 第14-15页 ·,点排名问题的研究现状 第15-19页 ·,边排名问题的研究现状 第19-24页 ·,- 连通的外平面图上的边排名 第20-22页 ·,树上的边排名 第22-24页
·,本章小结 第24-25页 第3章 树宽和度数均有界的图上的最小边排名问题 第25-40页 ·,将最小边排名问题转化为最小点排名问题 第25-27页 ·,求解树宽有界的图上的最小点排名问题 第27-38页 ·,求解树宽有界图的点排名判定问题 第27-36页 ·,树宽有界图的最小点排名的一个上界 第36-38页 ·,求树宽和度数均有界的图上的最小边排名问题 第38-39页 ·,本章小结 第39-40页 第4章 最小边排名问题的一个FPT算法 第40-45页 ·,求解最小边排名问题的一个FPT算法 第40-44页 ·,本章小结 第44-45页 第5章 结束语 第45-48页 ·,研究工作总结 第45-46页 ·,进一步研究工作 第46-48页 参考文献 第48-53页 致谢 第53-54页 研究成果 第54页