A simple local 3-approximation algorithm for vertex cover
type: Item
instance of: scholarly article
title: A simple local 3-approximation algorithm for vertex cover
zbMATH Open document ID: 1214.68468
author: Valentin Polishchuk
author: Jukka Suomela
published in: Information Processing Letters
publication date: 2010-08-16T00:00:00Z
full work available at URL: http://hdl.handle.net/10138/27927
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68W15
zbMATH DE Number: 5771279
zbMATH Keywords: approximation algorithms
zbMATH Keywords: distributed computing
zbMATH Keywords: graph algorithms
zbMATH Keywords: local algorithms
MaRDI profile type: Publication
OpenAlex ID: W2101781054
cites work: Fast Distributed Approximations in Planar Graphs
cites work: Q4250185
cites work: On the distributed complexity of computing maximal matchings
cites work: Efficient Distributed Weighted Matchings on Trees
cites work: What cannot be computed locally!
cites work: The price of being near-sighted
cites work: Leveraging Linial’s Locality Limit
cites work: Locality in Distributed Graph Algorithms
cites work: What Can be Computed Locally?
cites work: Linear programming without the matrix
cites work: Distributed Weighted Matching
DOI: 10.1016/J.IPL.2009.02.017
description: scientific article; zbMATH DE number 5771279