An optimal maximal independent set algorithm for bounded-independence graphs
type: Item
instance of: scholarly article
title: An optimal maximal independent set algorithm for bounded-independence graphs
zbMATH Open document ID: 1231.68092
author: J. Martínez
published in: Distributed Computing
publication date: 2010-09-09T00:00:00Z
full work available at URL: http://hdl.handle.net/20.500.11850/157549
Mathematics Subject Classification ID: 68M14
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68W15
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 5781472
zbMATH Keywords: ad hoc network
zbMATH Keywords: sensor network
zbMATH Keywords: radio network
zbMATH Keywords: unit disk graph
zbMATH Keywords: growth bounded graph
zbMATH Keywords: bounded-independence graph
zbMATH Keywords: local algorithm
zbMATH Keywords: parallel algorithm
zbMATH Keywords: maximal independent set
zbMATH Keywords: maximal matching
zbMATH Keywords: dominating set
zbMATH Keywords: connected dominating set
zbMATH Keywords: coloring
zbMATH Keywords: symmetry breaking
MaRDI profile type: Publication
OpenAlex ID: W1980501142
cites work: A fast and simple randomized parallel algorithm for the maximal independent set problem
cites work: Sorting in linear time?
cites work: Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
cites work: Deterministic coin tossing with applications to optimal parallel list ranking
cites work: Fast Distributed Approximations in Planar Graphs
cites work: A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
cites work: Parallel Symmetry-Breaking in Sparse Graphs
cites work: A fast and simple randomized parallel algorithm for maximal matching
cites work: Distributed Computing
cites work: On the locality of bounded growth
cites work: What cannot be computed locally!
cites work: Leveraging Linial’s Locality Limit
cites work: Locality in Distributed Graph Algorithms
cites work: A Simple Parallel Algorithm for the Maximal Independent Set Problem
cites work: A weakly robust PTAS for minimum clique partition in unit disk graphs
cites work: A log-star distributed maximal independent set algorithm for growth-bounded graphs
cites work: Coloring unstructured wireless multi-hop networks
cites work: Distributed agreement in tile self-assembly
DOI: 10.1007/S00446-010-0097-1
Recommended article: Q3128896
Recommended article: On the maximum independent set problem in graphs of bounded maximum degree
Recommended article: Algorithms for maximum independent set in convex bipartite graphs
Recommended article: A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs
Recommended article: Q4400853
Recommended article: Q3216150
Recommended article: An algorithm for finding a maximum weighted independent set in an arbitrary graph
Recommended article: Q4252376
Recommended article: Q5301767
Recommended article: Q4892322
description: scientific article; zbMATH DE number 5781472