An efficient parallel algorithm for computing a maximal independent set in a hypergraph of dimension 3

DOI10.1016/0020-0190(92)90228-NzbMath0764.68048MaRDI QIDQ1198086

Marek Karpinski, Pierre Kelsen, Elias Dahlhaus

Publication date: 16 January 1993

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

computational complexity; hypergraph; parallel algorithms; maximal independent set; NC algorithm

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C65: Hypergraphs

68R10: Graph theory (including graph drawing) in computer science

68W15: Distributed algorithms

Related Items

Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set, A global parallel algorithm for the hypergraph transversal problem, A simple NC-algorithm for a maximal independent set in a hypergraph of poly-log arboricity, On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of parallel search
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A New Parallel Algorithm for the Maximal Independent Set Problem
• Constructing a Maximal Independent Set in Parallel