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

DOI10.1007/BF01759072zbMath0731.68085MaRDI QIDQ808288

Marek Chrobak, Joseph (Seffi) Naor

Publication date: 1991

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

planar graphsindependent set

Mathematics Subject Classification ID

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

Related Items

Planar orientations with low out-degree and compaction of adjacency matrices, The maximum clique problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On linear-time algorithms for five-coloring planar graphs
• A fast parallel coloring of planar graphs with five colors
• Some simplified NP-complete graph problems
• A Linear Algorithm for Colouring Planar Graphs with Five Colours
• Parallel Symmetry-Breaking in Sparse Graphs
• Applications of a Planar Separator Theorem
• A linear 5-coloring algorithm of planar graphs
• An Approximation Algorithm for the Maximum Independent Set Problem on Planar Graphs
• Efficient Planarity Testing
• Every planar map is four colorable
• Optimal Parallel 5-Colouring of Planar Graphs
• A Theorem on Coloring the Lines of a Network