Set Cover, Set Packing and Hitting Set for Tree Convex and Tree-Like Set Systems

DOI10.1007/978-3-319-06089-7_17zbMath1405.68144OpenAlexW1007141672MaRDI QIDQ5410647

Guo-Hui Lin, Tian Liu, Min Lu, Ke Xu, Weitian Tong

Publication date: 16 April 2014

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-06089-7_17

zbMATH Keywords

NP-completenessset packingpolynomial timeset coverhitting settree-like set systemstree convex set systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Combinatorics in computer science (68R05) Combinatorial optimization (90C27)

Related Items (5)

Union Closed Tree Convex Sets ⋮ Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs ⋮ Maximum Edge Bicliques in Tree Convex Bipartite Graphs ⋮ On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT ⋮ On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT

This page was built for publication: Set Cover, Set Packing and Hitting Set for Tree Convex and Tree-Like Set Systems