顶点赋权区间图最重权路径问题研究

Research on the Maximum Weight Path of Vertex Weighted Interval Graphs

区间图是数轴上一组区间构成的相交图,由点、边构成,拥有清晰简洁的优美结构。区间表示与区间图一一对应,体现为一组区间的相交情况。在区间图G的对应区间表示I上,借助正规路径(NP),设计了一个多项式算法来解决顶点赋权区间图的最重权路径问题,该算法包含固定右端点的最重权路径的求解程序,证得在O(n3)运行时间内可解,其中n为输入区间图的顶点数,即可在多项式时间O(n3)内搜索并查找出一条给定赋权区间图上各顶点权值之和最大的路径。

Interval graph is an intersection graph composed of a group of intervals on the number line,which is composed of points and edges,and has a clear and concise beautiful structure.The interval representation corresponds to the interval graph one by one and is reflected as the intersection of a group of intervals.In the corresponding interval representation I of interval graph G,a polynomial algorithm is designed to solve the problem of the heaviest weight path of vertex weighted interval graph with the help of Normal Path(NP).The algorithm includes a solver for the heaviest weight path of the fixed right end point,which proves to be solvable in O(n3)running time,where n is the number of vertices in the input interval graph,it can search and find a path with the maximum sum of vertex weights on the given weighted interval graph in polynomial time.