討論串[請益] TWO Shortest Paths
共 15 篇文章
內容預覽:
<略>. <略>. 如果連點都不能重複, 找 disjoint connecting paths (甚至還不是 shortest). 這個問題會變成 NP-complete.. 請參閱. Computers and Intractability: A Guide to the Theory of N
(還有401個字)
內容預覽:
這問題應該可以 reduce 成 min-cost max-flow problem(更難).. 但是 min-cost max-flow 有 polynomial solution.. 所以可以證明這題不是 NP 問題.... reduce 方法:. 就把他想成 source 的 capacity
(還有36個字)
內容預覽:
Btw, 這個 reduction 看來不對喔.. vvv 你是說 destination 嗎?. ^^^^^^ 今天討論的是雙 source 版本. 目前你的 reduction 看來不完整,. 來問一個問題就可以知道你的 reduction 是怎麼一回事了.. 呃, 找到 max-flow 之後
(還有11個字)