Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover

DOI10.1016/j.disopt.2010.02.006zbMath1248.90069OpenAlexW2057208373MaRDI QIDQ456689

Peter Damaschke

Publication date: 16 October 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2010.02.006

zbMATH Keywords

solution spacevertex coverparameterized algorithmhypergraph transversal

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (5)

Minimum maximal acyclic matching in proper interval graphs ⋮ Parameterized complexity of computing maximum minimal blocking and hitting sets ⋮ On the complexity of minimum maximal acyclic matchings ⋮ Efficiently enumerating hitting sets of hypergraphs arising in data profiling ⋮ Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds

Cites Work

• An efficient fixed-parameter algorithm for 3-hitting set
• The union of minimal hitting sets: parameterized combinatorial bounds and counting
• Parameterized Algorithms for Hitting Set: The Weighted Case
• edge dominating set: Efficient Enumeration-Based Exact Algorithms
• Some Fixed-Parameter Tractable Classes of Hypergraph Duality and Related Problems
• Enumerate and Expand: New Runtime Bounds for Vertex Cover Variants
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Improved Parameterized Upper Bounds for Vertex Cover
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Parameterized algorithms for double hypergraph dualization with rank limitation and maximum minimal vertex cover