摘要
具有长度约束的简单路径(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 inDAGs,NLPDAG),NLPDAG算法可找到所有最长路径,对NLPDAG算法做进一步改进形成改进的NLPDAG算法,改进的NLPDAG算法可在线性时间复杂度内给出有向无环图中的一条最长路径.实验结果验证了NSPLCDAG和改进的NLPDAG算法的正确性与有效性.
The problem of Simple Paths with Length Constraint （SPLC） IS to calculate me num ber of simple paths between two vertices under the length constraint m in the graph. It is a special case of the h-path problem. In order to solve the problem in Directed Acyclic Graphs （DAGs）, this paper proposes an algorithm named Nettree for Simple Paths with Length Constraint in DAGs （NSPLCDAG） based on a data structure of Nettree which may have more than one root and one parent. First NSPLCDAG transforms the graph into a Nettree. Then the concept of the number of root paths of Nettree is used to solve the problem. Based on NSPLCDAG, a new algorithm named Nettree for the Longest Path in DAGs （NLPDAG） is constructed which can find all the longest paths. Then NLPDAG is improved and the improved NLPDAG can find one of the longest paths with linear time complexity. The experimental results verify the correctness and effectiveness of the two algorithms of NSPLCDAG and the improved NLPDAG.
出处
《计算机学报》
EI
CSCD
北大核心
2012年第10期2194-2203,共10页
Chinese Journal of Computers
基金
国家自然科学基金(61072100
51107029)
河北省自然科学基金(G2010000165)
河北省高等学校青年基金项目(SQ121006)资助~~
关键词
有向无环网络
简单路径
长度约束
最长路径
网树
directed acyclic graphs
simple path
length constraint
the longest path
nettree
