Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal

DOI10.1007/s40305-020-00335-4zbMath1488.05472OpenAlexW3119171189MaRDI QIDQ2059196

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

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

Cites Work

• Unnamed Item
• Kernelization for cycle transversal problems
• On the small cycle transversal of planar graphs
• Covering triangles in edge-weighted graphs
• Packing and covering triangles in planar graphs
• Packing and covering triangles in graphs
• Packing and covering triangles in tripartite graphs
• On a conjecture of Tuza about packing and covering of triangles
• Packing and covering triangles in \(K_{4}\)-free planar graphs
• A conjecture on triangles of graphs
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Sufficient Conditions for Tuza’s Conjecture on Packing and Covering Triangles
• On Generating Triangle-Free Graphs
• Total Dual Integrality of Triangle Covering
• Node-and edge-deletion NP-complete problems
• On the structure of linear graphs
• Approximating Maximum Subgraphs without Short Cycles

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