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

DOI10.1016/J.DISOPT.2010.02.006zbMATH Open1248.90069OpenAlexW2057208373MaRDI QIDQ456689FDOQ456689

Authors 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

vertex coverparameterized algorithmsolution spacehypergraph transversal

Mathematics Subject Classification ID

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

Recommendations

• Efficient algorithms for dualizing large-scale hypergraphs
• Efficient algorithms for dualizing large-scale hypergraphs
• Some Fixed-Parameter Tractable Classes of Hypergraph Duality and Related Problems
• Incremental complexity of a bi-objective hypergraph transversal problem
• Computing and Combinatorics

Cites work

• scientific article; zbMATH DE number 43754 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• An efficient fixed-parameter algorithm for 3-hitting set
• 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
• Parameterized Algorithms for Hitting Set: The Weighted Case
• Some Fixed-Parameter Tractable Classes of Hypergraph Duality and Related Problems
• The union of minimal hitting sets: parameterized combinatorial bounds and counting
• edge dominating set: Efficient Enumeration-Based Exact Algorithms

Cited in

(8)

• Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
• On the complexity of minimum maximal acyclic matchings
• Parameterized complexity of computing maximum minimal blocking and hitting sets
• Upper Clique Transversals in Graphs
• Efficiently enumerating hitting sets of hypergraphs arising in data profiling
• Minimum maximal acyclic matching in proper interval graphs
• An efficient graph technique based dual-type algorithm for NMNF problems with large capacity constraints
• On the complexity of minimum maximal acyclic matchings

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

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