Approximation algorithms on k-cycle transversal and k-clique transversal

DOI10.1007/S40305-020-00335-4MaRDI QIDQ2059196zbMATH OpenOpenAlexFDO

Authors Zhongzheng Tang, Zhuo Diao

Publication date 13 December 2021

Published in Journal of the Operations Research Society of China (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s40305-020-00335-4

zbMATH Keywords

approximation algorithms\(k\)-clique transversal\(k\)-cycle transversal

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Signed and weighted graphs (05C22) Transversal (matching) theory (05D15)

Recommendations

• Approximation algorithms for clique transversals on some graph classes
• Approximating Maximum Subgraphs without Short Cycles
• LP Approaches to Improved Approximation for Clique Transversal in Perfect Graphs
• Approximating maximum subgraphs without short cycles
• Approximability of clique transversal in perfect graphs

Cites work

• scientific article; zbMATH DE number 46849 (Why is no real title available?)
• A conjecture on triangles of graphs
• Approximating maximum subgraphs without short cycles
• Covering triangles in edge-weighted graphs
• Kernelization for cycle transversal problems
• Node-and edge-deletion NP-complete problems
• On a conjecture of Tuza about packing and covering of triangles
• On generating triangle-free graphs
• On the small cycle transversal of planar graphs
• On the structure of linear graphs
• Packing and covering triangles in \(K_{4}\)-free planar graphs
• Packing and covering triangles in graphs
• Packing and covering triangles in planar graphs
• Packing and covering triangles in tripartite graphs
• Sufficient conditions for Tuza's conjecture on packing and covering triangles
• Total dual integrality of triangle covering
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(9)

• Approximation algorithms for clique transversals on some graph classes
• Cycle Killer...Qu'est-ce que c'est? On the Comparative Approximability of Hybridization Number and Directed Feedback Vertex Set
• Approximating Maximum Subgraphs without Short Cycles
• Approximability of clique transversal in perfect graphs
• Approximating maximum subgraphs without short cycles
• The algorithmic complexity of the minus clique-transversal problem
• FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs
• LP Approaches to Improved Approximation for Clique Transversal in Perfect Graphs
• scientific article; zbMATH DE number 6297714 (Why is no real title available?)

This page was built for publication: Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal

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