Exact algorithms for finding minimum transversals in rank-3 hypergraphs

DOI10.1016/J.JALGOR.2004.01.001MaRDI QIDQ4736814zbMATH OpenOpenAlexFDO

Authors Magnus Wahlström

Publication date 6 August 2004

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

Full work available at URL https://doi.org/10.1016/j.jalgor.2004.01.001

zbMATH Keywords

3-Hitting SetExact algorithmHypergraphMinimum transversal

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Faster Algorithms to Enumerate Hypergraph Transversals
• Approximating minimum feedback vertex sets in hypergraphs
• An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals
• An efficient fixed-parameter algorithm for 3-hitting set
• Computing and Combinatorics

Cited in

(11)

• A bounded search tree algorithm for parameterized face cover
• Improved algorithms for the general exact satisfiability problem
• A faster algorithm for dominating set analyzed by the potential method
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• On sets of integers which contain no three terms in geometric progression
• Faster graph coloring in polynomial space
• A piecewise approach for the analysis of exact algorithms
• A piecewise approach for the analysis of exact algorithms
• Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
• A top-down approach to search-trees: Improved algorithmics for 3-hitting set
• Parameterized algorithms for d-hitting set: the weighted case

This page was built for publication: Exact algorithms for finding minimum transversals in rank-3 hypergraphs

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