Si dimostra la NP-completezza del problema della colorazione di spigoli di una certa classe di ipergrafi orientati. Tale colorazione generalizza la colorazione di grafi orientati già esistente in letteratura. Si dimostra anche la polinomialità della colorazione suddetta, per una sottoclasse di ipergrafi.
The complexity of arc-colorings for directed hypergraphs / Vietri, Andrea. - ELETTRONICO. - 17:(2004), pp. 281-284. (Intervento presentato al convegno CTW on Graphs and Combinatorial Optimization tenutosi a Milano nel 31 maggio - 2 giugno 2004) [10.1016/j.endm.2004.03.056].
The complexity of arc-colorings for directed hypergraphs
VIETRI, Andrea
2004
Abstract
Si dimostra la NP-completezza del problema della colorazione di spigoli di una certa classe di ipergrafi orientati. Tale colorazione generalizza la colorazione di grafi orientati già esistente in letteratura. Si dimostra anche la polinomialità della colorazione suddetta, per una sottoclasse di ipergrafi.File allegati a questo prodotto
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
