A simple NC-algorithm for a maximal independent set in a hypergraph of poly-log arboricity
From MaRDI portal
Publication:1350189
DOI10.1016/0020-0190(96)00040-3zbMath0900.68237MaRDI 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
Related Items
Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set, A global parallel algorithm for the hypergraph transversal problem, 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
- 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