riduzione semplice (NP completezza)

Question

sto cercando un mezzo per dimostrare che la bicriteria problema del cammino minimo è NP completo. Cioè, in un grafico con lunghezze e pesi, devo sapere se un esiste un cammino nel grafo da s a t con lunghezza totale <= L e peso <= W.

So che devo prendere un problema NP completo e ridurlo a questo. Abbiamo a nostra disposizione i seguenti problemi tra cui scegliere:. 3-SAT, insieme indipendente, della copertura dei vertici, ciclo hamiltoniano, e la congruenza 3-dimensionale

Tutte le idee su cui possono essere vitali?

grazie

Answer 1

Hai provato Google? 3 ° colpo è:

http: //www.jstage.jst .go.jp / articolo / ieejeiss / 128/3 / 128_416 / _article

L'articolo è pay-per-view, ma la cache di Google alimenta il bit importante in anticipo:

"Purtroppo, il caso multiobiettivo (compreso il caso bicriteria) è NP-completo (3).

ed i punti di riferimento a:

(3) M. Garey e D. Johnson: Computer, e Intrattabilità: Una guida per la teoria della NP-Completezza, New York: Freeman (1979)

, che è lo standard di riferimento per le questioni di questa forma.

Quindi ... hai guardato Garey e Johnson? Non ho una copia qui per controllare, ma era la mia go-to quando ho fatto composizioni.