Ravvicinamento delle banda minima su alberi binari

Question

problema minima di banda è quello di un trovare un ordinamento dei nodi del grafo on line intero che riduce al minimo la più grande distanza tra due nodi adiacenti.

Il problema decisionale è NP-completo anche per gli alberi binari. Risultati complessità per larghezza di banda Minimizzazione. Garey, Graham, Johnson e Knuth, SIAM J. Appl. Math., Vol. 34, No.3 1978 .

Qual è il miglior risultato noto approssimabilità efficiente per il calcolo della larghezza di banda minima su alberi binari? Ciò che è meglio conosciuto durezza condizionale di risultato approssimazione?

Answer 1

Blache et. al, per il ravvicinamento Intrattabilità della larghezza di banda Problem 1997 conferma non c'è PTAS per il problema a meno che $ \ text {P} = \ text {NP} $, anche per (binario) alberi. Unger W, la complessità del ravvicinamento del Bandwidth problema, 1998 mostrano che per qualsiasi costante k $ \ in \ mathbb {N} $ non v'è alcun algoritmo polinomiale approssimazione il tempo con un fattore di approssimazione di $ k $. Così, purtroppo, non c'è PTAS e non APX per il problema.

Tuttavia, per alcuni tipi di grafici, il problema può essere risolto o approssimata in tempo polinomiale. Per un recente sondaggio, vedi Petit J., Addenda l'indagine di problemi di layout 2011 . Nel sondaggio, vedi tabelle 3, 4 e 8. L'indagine fornisce anche una bella lista di riferimenti se si vuole scavare più a fondo in una certa direzione. Si tratta di una versione più aggiornata del sondaggio più vecchio da Diaz et al. , Un sondaggio di problemi di layout grafico, 2002 .

Nel caso in cui ti interessa l'algoritmo esatto così, penso che attualmente quella più veloce è dato da Cygan M. e Pilipczuk M., ancora più veloce Esatto Bandwidth 2012 . Le piste algoritmo a $ O (4.83 ^ n) $ tempo.