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

DOI10.1007/B13810MaRDI QIDQ5897355zbMATHOpenAlexFDO

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

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)

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

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)