In this paper we study the problem of computing approximate vertex covers of a graph on the basis of partial information in the distributed decision-making model proposed by Deng and Papadimitriou [1]. In particular, we show an optimal algorithm whose competitive ratio is equal to p, where p is the number of processors.
ON THE DISTRIBUTED DECISION-MAKING COMPLEXITY OF THE MINIMUM VERTEX COVER PROBLEM / P. CRESCENZI; L. TREVISAN. - In: RAIRO. INFORMATIQUE THEORIQUE ET APPLICATIONS. - ISSN 0988-3754. - STAMPA. - 30:(1996), pp. 431-441. [10.1051/ita/1996300504311]
ON THE DISTRIBUTED DECISION-MAKING COMPLEXITY OF THE MINIMUM VERTEX COVER PROBLEM
CRESCENZI, PIERLUIGI;
1996
Abstract
In this paper we study the problem of computing approximate vertex covers of a graph on the basis of partial information in the distributed decision-making model proposed by Deng and Papadimitriou [1]. In particular, we show an optimal algorithm whose competitive ratio is equal to p, where p is the number of processors.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
