Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs
From MaRDI portal
Publication:1944214
DOI10.1016/j.ipl.2011.09.007zbMath1260.68157MaRDI QIDQ1944214
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
68R10: Graph theory (including graph drawing) in computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68W25: Approximation algorithms
Related Items
The clique-transversal set problem in \(\{\mathrm{claw},K_4\}\)-free planar 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, The vertex cover \(P_3\) problem in cubic graphs
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