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

DOI10.1016/J.IPL.2011.09.007MaRDI QIDQ1944214zbMATH OpenOpenAlexFDO

Authors 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 algorithmclique-independent setclique-transversal setcubic graphNP-complete

Mathematics Subject Classification ID

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

Recommendations

• Clique-Transversal Sets in Cubic Graphs
• Approximation algorithms for clique transversals on some graph classes
• Clique-transversal sets in line graphs of cubic graphs and triangle-free graphs
• Claw-free cubic graphs with clique-transversal number half of their order
• The clique-transversal set problem in \(\{\mathrm{claw},K_4\}\)-free planar graphs

Cites work

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

Cited in

(10)

• Complete-subgraph-transversal-sets problem on bounded treewidth graphs
• Approximation algorithms for clique transversals on some graph classes
• The vertex cover \(P_3\) problem in cubic graphs
• LP Approaches to Improved Approximation for Clique Transversal in Perfect Graphs
• The clique-transversal set problem in \(\{\mathrm{claw},K_4\}\)-free planar graphs
• Clique-Transversal Sets in Cubic Graphs
• An approximation algorithm for the maximum independent set problem in cubic planar graphs
• A fixed-parameter algorithm for the vertex cover P₃ problem
• The clique-transversal set problem in claw-free graphs with degree at most 4
• Approximability of clique transversal in perfect graphs

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

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