首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Two disjoint shortest paths problem with non-negative edge length
Authors:Yusuke Kobayashi  Ryo Sako
Abstract:In the two disjoint shortest paths problem ( 2-DSPP), the input is a graph (or a digraph) and its vertex pairs (s1,t1) and (s2,t2), and the objective is to find two vertex-disjoint paths P1 and P2 such that Pi is a shortest path from si to ti for i=1,2, if they exist. In this paper, we give a first polynomial-time algorithm for the undirected version of the 2-DSPP with an arbitrary non-negative edge length function.
Keywords:Corresponding author    Disjoint paths  Shortest path  Polynomial-time algorithm
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号