Packing Cuts in Graphs,
in preparation
descrizione: Diamo svariati risultati di inapprossimabilitá per il problema di trovare il maggior numero possibile di tagli disgiunti in un dato grafo. La questione dell' NP-hardness del problema era stata recentemente posta al centro dell'attenzione da alcuni lavori di Ajeev, ma segue ora come conseguenza di questi ben piú forti risultati. (Non approssimabilitá entro un fattore
nel caso generale
ed APX-hardness in svariati casi particolari).
Diamo altresí degli algoritmi approssimati che mostrano
come tali risultati siano stretti.
Packing triangles in planar graphs,
ready for submission
descrizione: Dato un grafo planare, vogliamo trovare in esso il massimo numero di triangoli disgiunti. A seconda che li si voglia solamente disgiunti sui nodi od anche sugli archi abbiamo due distinti problemi. Tuttavia, in una trattazione assai unificata, diamo dei PTAS per entrambi i problemi avvalendoci del teorema separatore. Un PTAS é un algoritmo approssimante a qual si voglia precisione ed é in pratica il meglio che si possa sperare quando il problema in questione risulti essere NP-hard. In effetti noi si dimostra inoltre che entrambi i problemi sono NP-hard. Precedentemente solamente il caso di triangoli disgiunti sui nodi era noto essere tale e la dimostrazione basava su una ben piú complessa riduzione che non quella da noi proposta.
