Anzeige
Erschienen in:
1995 | ReviewPaper | Buchkapitel
Minimum vertex cover, distributed decision-making, and communication complexity
Extended abstract
verfasst von : Pierluigi Crescenzi, Luca Trevisan
Erschienen in: Graph-Theoretic Concepts in Computer Science
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.