主講者:	李建平教授 (雲南大學)
講題:	The Strongly Polynomial-Time Solvability of the Next-to-Shortest Path Problem for Positively Weighted Digraphs
時間:	2013-03-08 (Fri.)  14:00 - 15:30
地點:	數學所 617 研討室 (台大院區)
Abstract:	In this talk, we consider the problem of computing a next-to-shortest path in a weighted digraph with positive weights. The problem is defined as follows. Given any weighted digraph $D=(V,A;w;s,t)$ and two prescribed vertices $s$ and $t$, where $w: A \rightarrow R^+$ is a weight function, a next-to-shortest $(s,t)$-path is a shortest $(s,t)$-path among all $(s,t)$-paths having length strictly greater than the length of a shortest $(s,t)$-path in the digraph $D$. An open question proposed in Kao et~al. (Algorithmica ${\bf 61}$, 402--418, 2011) asks whether there exists a polynomial-time algorithm to compute a next-to-shortest $(s,t)$-path in a digraph $D$ with positive weights. In this paper, we answer this question in the affirmative. More precisely, we can design a strongly polynomial-time algorithm with running time ${\cal O}(|V|^4|A|)$ to either compute a next-to-shortest $(s,t)$-path or determine that none exists in the digraph $D$.
	|| Close window ||