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

Research on the Maximum Weight Path of Vertex Weighted Interval Graphs

作　　者：周星利 李鹏 ZHOU Xingli;LI Peng(College of Science,Chongqing University of Technology,Chongqing 400054,China)

机构地区：[1]重庆理工大学理学院,重庆400054

出　　处：《内蒙古民族大学学报（自然科学版）》2024年第6期24-31,共8页Journal of Inner Mongolia Minzu University：Natural Sciences Edition

基　　金：国家自然科学基金项目(11701059);重庆市教委科技研究计划青年项目(KJQN202101130);重庆市研究生科研创新项目(CYS23687)。

摘　　要：区间图是数轴上一组区间构成的相交图,由点、边构成,拥有清晰简洁的优美结构。区间表示与区间图一一对应,体现为一组区间的相交情况。在区间图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.

关 键 词：区间图 顶点赋权 最重权路径 多项式算法 动态算法 

分 类 号：O157.5[理学—数学]