Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs

DOI10.1016/j.ipl.2011.09.007zbMath1260.68157OpenAlexW2003253430MaRDI QIDQ1944214

Zuosong Liang, Erfang Shan

Publication date: 4 April 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2011.09.007

zbMATH Keywords

approximation algorithmcubic graphNP-completeclique-independent setclique-transversal set

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (6)

The clique-transversal set problem in \(\{\mathrm{claw},K_4\}\)-free planar graphs ⋮ The vertex cover \(P_3\) problem in cubic graphs ⋮ A fixed-parameter algorithm for the vertex cover \(P_3\) problem ⋮ The clique-transversal set problem in claw-free graphs with degree at most 4 ⋮ Complete-subgraph-transversal-sets problem on bounded treewidth graphs ⋮ Approximation algorithms for clique transversals on some graph classes

Cites Work

• Unnamed Item
• Bounds on the clique-transversal number of regular graphs
• Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs
• Covering the cliques of a graph with vertices
• On clique-transversals and clique-independent sets
• Algorithmic aspects of clique-transversal and clique-independent sets
• Distance-hereditary graphs are clique-perfect
• On balanced graphs
• Minimum Edge Dominating Sets
• Clique-Transversal Sets in Cubic Graphs
• Algorithmic Aspects of Neighborhood Numbers

This page was built for publication: Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs