A global parallel algorithm for the hypergraph transversal problem

DOI10.1016/j.ipl.2006.09.006zbMath1185.68838OpenAlexW2008756825MaRDI QIDQ845919

Endre Boros, Khaled M. Elbassioni, Leonid G. Khachiyan, Vladimir A. Gurvich

Publication date: 29 January 2010

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2006.09.006

zbMATH Keywords

hypergraphdualizationparallel processingmaximal independent setbounded dimensionconformal hypergraphglobal parallel algorithmincremental generatingminimal transversal

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Related Items (12)

The adjacency matrix of a graph as a data table: a geometric perspective ⋮ The Minimal Hitting Set Generation Problem: Algorithms and Computation ⋮ Upper transversals in hypergraphs ⋮ A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs ⋮ Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic ⋮ On the complexity of monotone dualization and generating minimal hypergraph transversals ⋮ Scientific contributions of Leo Khachiyan (a short overview) ⋮ On the completability of incomplete Latin squares ⋮ Polynomial-time dualization of \(r\)-exact hypergraphs with applications in geometry ⋮ Bounds on upper transversals in hypergraphs ⋮ Affine planes and transversals in 3-uniform linear hypergraphs ⋮ Efficiently enumerating hitting sets of hypergraphs arising in data profiling

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorial characterization of read-once formulae
• Dualization of regular Boolean functions
• The complexity of parallel search
• An efficient parallel algorithm for computing a maximal independent set in a hypergraph of dimension 3
• Exact transversal hypergraphs and application to Boolean \(\mu\)-functions
• A simple NC-algorithm for a maximal independent set in a hypergraph of poly-log arboricity
• Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms
• Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries
• Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities
• New results on monotone dualization and generating hypergraph transversals
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A fast parallel algorithm for the maximal independent set problem
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• A Parallel Randomized Algorithm for Finding a Maximal Independent Set in a Linear Hypergraph
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Dual subimplicants of positive Boolean functions
• LATIN 2004: Theoretical Informatics

This page was built for publication: A global parallel algorithm for the hypergraph transversal problem