An efficient parallel algorithm for computing a large independent set in a planar graph

DOI10.1007/BF01759072MaRDI QIDQ808288zbMATH OpenFDO

Authors Marek Chrobak, Joseph (Seffi) Naor

Publication date 1991

Published in Algorithmica (Search for Journal in Brave)

zbMATH Keywords

independent setplanar graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

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

Cites work

• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3400923 (Why is no real title available?)
• A Linear Algorithm for Colouring Planar Graphs with Five Colours
• A Theorem on Coloring the Lines of a Network
• A fast parallel coloring of planar graphs with five colors
• A linear 5-coloring algorithm of planar graphs
• An Approximation Algorithm for the Maximum Independent Set Problem on Planar Graphs
• Applications of a Planar Separator Theorem
• Efficient Planarity Testing
• Every planar map is four colorable
• On linear-time algorithms for five-coloring planar graphs
• Optimal Parallel 5-Colouring of Planar Graphs
• Parallel Symmetry-Breaking in Sparse Graphs
• Some simplified NP-complete graph problems

Cited in

(6)

• Planar orientations with low out-degree and compaction of adjacency matrices
• Parallel algorithms for fractional and maximal independent sets in planar graphs
• An Efficient Parallel Algorithm that Finds Independent Sets of Guaranteed Size
• The maximum clique problem
• A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs
• Computing transparently: The independent sets in a graph

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)