On the distributed decision-making complexity of the minimum vertex cover problem

DOI10.1051/ITA/1996300504311MaRDI QIDQ3126012zbMATH OpenOpenAlexFDO

Authors Pilu Crescenzi, Luca Trevisan

Publication date 4 December 1997

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/92544

zbMATH Keywords

distributed decision-making modelvertex covers

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Parallel algorithms in computer science (68W10)

Recommendations

• A Local 2-Approximation Algorithm for the Vertex Cover Problem
• Approximated distributed minimum vertex cover algorithms for bounded degree graphs
• A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds
• A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds
• Computing and Combinatorics

Cites work

• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Linear programming without the matrix
• On the value of information in distributed decision-making (extended abstract)
• The Complexity of the Lin–Kernighan Heuristic for the Traveling Salesman Problem

Cited in

(2)

• Competitive distributed decision-making
• Minimum vertex cover, distributed decision-making, and communication complexity

This page was built for publication: On the distributed decision-making complexity of the minimum vertex cover problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3126012)