A global parallel algorithm for the hypergraph transversal problem

DOI10.1016/J.IPL.2006.09.006zbMATH Open1185.68838OpenAlexW2008756825MaRDI QIDQ845919FDOQ845919

Authors: Endre Boros, Khaled Elbassioni, Leonid G. Khachiyan, Vladimir 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

Recommendations

• Computing and Combinatorics
• A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs
• An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation
• Faster Algorithms to Enumerate Hypergraph Transversals
• An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals

zbMATH Keywords

hypergraphmaximal independent setparallel processingdualizationbounded 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)

Cites Work

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

Cited In (18)

• Polynomial-time dualization of \(r\)-exact hypergraphs with applications in geometry
• Computing and Combinatorics
• On the complexity of monotone dualization and generating minimal hypergraph transversals
• The adjacency matrix of a graph as a data table: a geometric perspective
• Upper transversals in hypergraphs
• On the completability of incomplete Latin squares
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• An average study of hypergraphs and their minimal transversals
• A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs
• Achieving new upper bounds for the hypergraph duality problem through logic
• Affine planes and transversals in 3-uniform linear hypergraphs
• Efficiently enumerating hitting sets of hypergraphs arising in data profiling
• Minimal solutions of fuzzy relation equations via maximal independent elements
• A data mining formalization to improve hypergraph minimal transversal computation
• The minimal hitting set generation problem: algorithms and computation
• Title not available (Why is that?)
• Scientific contributions of Leo Khachiyan (a short overview)
• Bounds on upper transversals in hypergraphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q845919)