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.
Graph-Theoretic Concepts in Computer Science
TWENTIETH INTERNATIONAL WORKSHOP ON GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE
P. CRESCENZI; L. TREVISAN
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.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2158/237688
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact