Set cover, set packing and hitting set for tree convex and tree-like set systems

DOI10.1007/978-3-319-06089-7_17MaRDI QIDQ5410647zbMATH OpenOpenAlexFDO

Authors Min Lu, Tian Liu, Weitian Tong, Guohui Lin, Ke Xu

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 coverpolynomial timeset packinghitting settree-like set systemstree convex set systems

Mathematics Subject Classification ID

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

Recommendations

• Exact algorithms and applications for tree-like Weighted Set Cover
• A review of tree convex sets test
• On nontrivial covers and partitions of graphs by convex sets
• Union closed tree convex sets
• On structural parameterizations of \textsc{Hitting Set}: hitting paths in graphs using 2-SAT

Cited in

(6)

• Maximum Edge Bicliques in Tree Convex Bipartite Graphs
• Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
• On structural parameterizations of Hitting Set: hitting paths in graphs using 2-SAT
• A review of tree convex sets test
• On structural parameterizations of \textsc{Hitting Set}: hitting paths in graphs using 2-SAT
• Union closed tree convex sets

This page was built for publication: Set cover, set packing and hitting set for tree convex and tree-like set systems

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