A Parallel Randomized Algorithm for Finding a Maximal Independent Set in a Linear Hypergraph

DOI10.1006/jagm.1997.0884zbMath0887.68048OpenAlexW2010583864MaRDI QIDQ4373005

Edyta Szymańska, Tomasz Łuczak

Publication date: 25 May 1998

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jagm.1997.0884

zbMATH Keywords

randomized parallel algorithm

Mathematics Subject Classification ID

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

Related Items (4)

A global parallel algorithm for the hypergraph transversal problem ⋮ On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs ⋮ On vertex independence number of uniform hypergraphs ⋮ Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set

This page was built for publication: A Parallel Randomized Algorithm for Finding a Maximal Independent Set in a Linear Hypergraph