Content deleted Content added
→Reduction from an NP-Complete problem?: I think I figured it out. Could someone verify? |
|||
Line 91:
The lead cites a reduction by Sedgewick from the [[NP-Complete]] [[Hamiltonian path problem]] to the [[shortest path problem]]. Since the shortest path problem (even <ins>for all-pairs</ins> with <ins>edges of</ins> negative weight<del>s</del>) is not NP-Complete (i.e., Floyd-Warshall = O(n^3)), something needs to be clarified/corrected. <b>[[User:Justin W Smith|Justin W Smith]]</b> <i><sup>[[User talk:Justin W Smith|talk]]</sup>/<sub>[[Special:Contributions/Justin W Smith|stalk]]</sub></i> 06:15, 21 April 2010 (UTC)
: I think I figured out what was being said. If someone could verify this, I would appreciate it. <b>[[User:Justin W Smith|Justin W Smith]]</b> <i><sup>[[User talk:Justin W Smith|talk]]</sup>/<sub>[[Special:Contributions/Justin W Smith|stalk]]</sub></i> 14:08, 21 April 2010 (UTC)
| |||