In this paper we study the problem of computing approximate vertex covers of a graph on the basis of partial information and we consider the distributed decision-making and the communication complexity frameworks. In the first framework we do not allow communication among the processors: in this case, we show an optimal algorithm whose performance ratio is equal to p where p is the number of processors. In the second framework two processors are allowed to communicate in order to find an approximate solution: in this latter case, we show a linear lower bound on the communication complexity of the problem.
MINIMUM VERTEX COVER, DISTRIBUTED DECISION-MAKING, AND COMMUNICATION COMPLEXITY / P. CRESCENZI; L. TREVISAN. - STAMPA. - (1994), pp. 130-139. (Intervento presentato al convegno TWENTIETH INTERNATIONAL WORKSHOP ON GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE).
MINIMUM VERTEX COVER, DISTRIBUTED DECISION-MAKING, AND COMMUNICATION COMPLEXITY
CRESCENZI, PIERLUIGI;
1994
Abstract
In this paper we study the problem of computing approximate vertex covers of a graph on the basis of partial information and we consider the distributed decision-making and the communication complexity frameworks. In the first framework we do not allow communication among the processors: in this case, we show an optimal algorithm whose performance ratio is equal to p where p is the number of processors. In the second framework two processors are allowed to communicate in order to find an approximate solution: in this latter case, we show a linear lower bound on the communication complexity of the problem.I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.