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 complexityhypergraphparallel algorithmsmaximal independent setNC algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Related Items (4)

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 ⋮ Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set

Cites Work

• 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
• Unnamed Item
• Unnamed Item

This page was built for publication: An efficient parallel algorithm for computing a maximal independent set in a hypergraph of dimension 3