An efficient parallel algorithm for computing a large independent set in a planar graph
From MaRDI portal
Publication:808288
DOI10.1007/BF01759072zbMATH Open0731.68085MaRDI QIDQ808288FDOQ808288
Authors: Marek Chrobak, Joseph (Seffi) Naor 
Publication date: 1991
Published in: Algorithmica (Search for Journal in Brave)
Recommendations
- Parallel algorithms for fractional and maximal independent sets in planar graphs
- A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs
- A fast parallel algorithm for the maximal independent set problem
- An Efficient Parallel Algorithm that Finds Independent Sets of Guaranteed Size
- Parallel approximation schemes for problems on planar graphs
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Applications of a Planar Separator Theorem
- Efficient Planarity Testing
- Some simplified NP-complete graph problems
- Every planar map is four colorable
- An Approximation Algorithm for the Maximum Independent Set Problem on Planar Graphs
- A Theorem on Coloring the Lines of a Network
- Title not available (Why is that?)
- Parallel Symmetry-Breaking in Sparse Graphs
- Optimal Parallel 5-Colouring of Planar Graphs
- On linear-time algorithms for five-coloring planar graphs
- A fast parallel coloring of planar graphs with five colors
- A Linear Algorithm for Colouring Planar Graphs with Five Colours
- A linear 5-coloring algorithm of planar graphs
Cited In (6)
- Computing transparently: The independent sets in a graph
- The maximum clique problem
- A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs
- Planar orientations with low out-degree and compaction of adjacency matrices
- An Efficient Parallel Algorithm that Finds Independent Sets of Guaranteed Size
- Parallel algorithms for fractional and maximal independent sets in planar graphs
This page was built for publication: An efficient parallel algorithm for computing a large independent set in a planar graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q808288)
