A work-optimal coarse-grained PRAM algorithm for Lexicographically First Maximal Independent Set.

DOI10.1007/B13810zbMATH Open1257.68142OpenAlexW3144329707MaRDI QIDQ5897355FDOQ5897355

Authors: Jens Gustedt, Jan Arne Telle 

Publication date: 23 February 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/b13810

Recommendations

• A fast parallel algorithm for the maximal independent set problem
• Constructing a Maximal Independent Set in Parallel
• scientific article; zbMATH DE number 219239
• A New Parallel Algorithm for the Maximal Independent Set Problem
• Parallel algorithms for fractional and maximal independent sets in planar graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Parallel algorithms in computer science (68W10)

Cited In (1)

• A measure for the lexicographically first maximal independent set problem and its limits

This page was built for publication: A work-optimal coarse-grained PRAM algorithm for Lexicographically First Maximal Independent Set.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5897355)