原书出处
Introduction to Algorithms, Fourth Edition
34 第34章 NP完全性
open research problems in theoretical computer science since it was first posed in 1971.
Several NP-complete problems are particularly tantalizing because they seem on the surface to be similar to problems that we know how to solve in polynomial time. In each of the following pairs of problems, one is solvable in polynomial time and the other is NP-complete, but the difference between the problems appears to be slight: Shortest versus longest simple paths: In Chapter 22, we saw that even with negative edge weights, we can find shortest paths from a single source in a directed graph G = (V, E) in O(VE) time. Finding a longest simple path between two vertices is difficult, however. Merely determining whether a graph contains a simple path with at least a given number of edges is NP-complete. Euler tour versus hamiltonian cycle: An Euler tour of a strongly connected, directed graph G = (V, E) is a cycle that traverses each edge of G exactly once, although it is allowed to visit each vertex more than once. Problem 20-3 on page 583 asks you to show how to determine whether a strongly connected, directed graph has an
Euler tour and, if it does, the order of the edges in the Euler tour, all in O(E) time. A
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/Introduction to Algorithms, Fourth Edition/_epub-src/OEBPS/chapter034.xhtml
EPUB SHA-256:ec7ced04bb875b93983816aef7a667855a4b71c5cf53b63406b9439c74e27aea