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 algorithmcubic graphNP-completeclique-independent setclique-transversal set

Mathematics Subject Classification ID

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

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 Neighborhood Numbers
• Algorithmic aspects of clique-transversal and clique-independent sets
• Bounds on the clique-transversal number of regular graphs
• Clique-Transversal Sets in Cubic Graphs
• Clique-transversal sets and weak 2-colorings in graphs of small maximum degree
• 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)

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