标题:一类双约束最短路问题的近似算法
作者:于立勇;李曙光
作者机构:[于立勇] 山东大学数学与系统科学学院, 济南, 山东 250100, 中国.;[李曙光] 山东大学数学与系统科学学院, 济南, 山东 250100, 中国 更多
来源:山东大学学报. 理学版
出版年:2002
卷:37
期:4
页码:304-306+311
关键词:最短路问题; 约束; 动态规划; 全多项时间近似方案
摘要:带时间和边数约束的双约束最短路问题是NP-完备的。它的一种拟多项式精确算法可以利用动态规划方法给出,在此基础上采用rounding和scalin g的处理技术得到了一种全多项式时间近似方案(FPAS)。
收录类别:CSCD
资源类型:期刊论文
原文链接:http://kns.cnki.net/kns/detail/detail.aspx?FileName=SDDX200204006&DbName=CJFQ2002
TOP