A simple NC-algorithm for a maximal independent set in a hypergraph of poly-log arboricity

DOI10.1016/0020-0190(96)00040-3zbMath0900.68237OpenAlexW2069194665MaRDI QIDQ1350189

Andrzej Lingas, Pierre Kelsen, Oscar Garrido

Publication date: 27 February 1997

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

Full work available at URL: https://doi.org/10.1016/0020-0190(96)00040-3

zbMATH Keywords

Parallel algorithmsMaximal independent setHypergraph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Related Items (3)

A global parallel algorithm for the hypergraph transversal problem ⋮ 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

• Unnamed Item
• Unnamed Item
• The complexity of parallel search
• An efficient parallel algorithm for computing a maximal independent set in a hypergraph of dimension 3
• Removing randomness in parallel computation without a processor penalty
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast parallel algorithm for the maximal independent set problem
• Parallel Symmetry-Breaking in Sparse Graphs
• Constructing a Maximal Independent Set in Parallel

This page was built for publication: A simple NC-algorithm for a maximal independent set in a hypergraph of poly-log arboricity