This paper resolves the parallel complexity of the graph closure problem, an open question posed by S. Khuller. In particular, we prove that the 2N - k-closure problem is in L for k = 5 and it is P-complete for k greater than or equal to 6. Finally, we show that the N + k-closure problem is P-complete for any integer k.
On the computational complexity of graph closures / Monti, Angelo. - In: INFORMATION PROCESSING LETTERS. - ISSN 0020-0190. - STAMPA. - 57:6(1996), pp. 291-295. [10.1016/0020-0190(96)00027-0]
On the computational complexity of graph closures
MONTI, Angelo
1996
Abstract
This paper resolves the parallel complexity of the graph closure problem, an open question posed by S. Khuller. In particular, we prove that the 2N - k-closure problem is in L for k = 5 and it is P-complete for k greater than or equal to 6. Finally, we show that the N + k-closure problem is P-complete for any integer k.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.
