A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs

DOI10.1016/0304-3975(88)90106-5zbMath0655.68086OpenAlexW1992702935MaRDI QIDQ1109576

Xin He

Publication date: 1988

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(88)90106-5

zbMATH Keywords

planar graphsparallel algorithmmaximal independent set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Finding small simple cycle separators for 2-connected planar graphs
• A batching method for coloring planar graphs
• A taxonomy of problems with fast parallel algorithms
• An Efficient Parallel Biconnectivity Algorithm
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A Nearly Optimal Parallel Algorithm for Constructing Depth First Spanning Trees in Planar Graphs
• A Scheme for Fast Parallel Communication
• An O(logn) parallel connectivity algorithm
• Optimal Search in Planar Subdivisions