网树求解有向无环图中具有长度约束的简单路径和最长路径问题

摘要：

具有长度约束的简单路径(Simple Paths with Length Constraint,SPLC)问题是指求解图中任意两点间路径长度为m的简单路径数,是k-path问题的一种特殊情况.该文基于网树数据结构提出了在有向无环图中求解SPLC问题的算法(Nettree for SPLC in Directed Acyclic Graphs,NSPLCDAG).网树是一种多树根多双亲的数据结构.NSPLCDAG算法将该问题转化为一棵网树后,利用树根路径数这一性质对其进行求解.对NSPLCDAG算法进行改造,可以求解有向无环图中最长路径问题并形成网树求解最长路径算法(Nettree for the Longest Path in DAGs,NLPDAG),NLPDAG算法可找到所有最长路径,对NLPDAG算法做进一步改进形成改进的NLPDAG算法,改进的NLPDAG算法可在线性时间复杂度内给出有向无环图中的一条最长路径.实验结果验证了NSPLCDAG和改进的NLPDAG算法的正确性与有效性.

关键词：有向无环网络、简单路径、长度约束、最长路径、网树

所属期刊栏目：35

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金61072100,51107029;河北省自然科学基金G2010000165;河北省高等学校青年基金项目SQ121006

在线出版日期：2012-12-17（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：2194-2203