c*x
发帖数: 555 | 1 An airline network is represented by a weighted digraph G=(V,E) in which
airports are denoted by vertices, flight legs are denoted by edges, and flight
time (or geological distance) is denoted by a weight. Suppose that the airline
company wants to establish k repair facilities at certain airports so that
every airport can receive repair service reasonably. The distance d(u,v) from
vertex u to vertex v is defined as the length of a shortest path from u to v
on G.
Input:
weighted digraph G=(V,E)
p | c*x
发帖数: 555 | 2 Yeah they are similar. The only difference is "facility location problem"
http://www.ms.ic.ac.uk/jeb/or/facloc.html asks for minimum TOTAL cost
of serving all, while this one asks if each service cost is less than a
threshhold D.
Here's a very good summary for NP-complete problem feature and proof.
I wonder if I can use the 3rd proof method there:
(
Method #3 (restriction; simple but not always available to all problems)
(a) P is in NP.
(b) Find a special case of P is in NP-Complete.
Ex | k**y
发帖数: 320 | 3 这是一个成题，结论早就有了。希望下面的LINK对你有帮助。
http://www.nada.kth.se/~viggo/wwwcompendium/node132.html
G
and
E?
with
that
to
【在 c*x 的大作中提到】
: Yeah they are similar. The only difference is "facility location problem"
: http://www.ms.ic.ac.uk/jeb/or/facloc.html asks for minimum TOTAL cost
: of serving all, while this one asks if each service cost is less than a
: threshhold D.
: Here's a very good summary for NP-complete problem feature and proof.
: I wonder if I can use the 3rd proof method there:
: (
:
: Method #3 (restriction; simple but not always available to all problems)
: (a) P is in NP.
|
|
