Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs
type: Item
instance of: scholarly article
title: Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs
zbMATH Open document ID: 1260.68157
author: Zuosong Liang
author: Erfang Shan
published in: Information Processing Letters
publication date: 2013-04-04T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 6150501
zbMATH Keywords: clique-transversal set
zbMATH Keywords: clique-independent set
zbMATH Keywords: approximation algorithm
zbMATH Keywords: NP-complete
zbMATH Keywords: cubic graph
MaRDI profile type: Publication
full work available at URL: j.ipl.2011.09.007
OpenAlex ID: W2003253430
cites work: Q3575455
cites work: Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs
cites work: On balanced graphs
cites work: Algorithmic Aspects of Neighborhood Numbers
cites work: On clique-transversals and clique-independent sets
cites work: Covering the cliques of a graph with vertices
cites work: Algorithmic aspects of clique-transversal and clique-independent sets
cites work: Minimum Edge Dominating Sets
cites work: Distance-hereditary graphs are clique-perfect
cites work: Clique-Transversal Sets in Cubic Graphs
cites work: Bounds on the clique-transversal number of regular graphs
DOI: 10.1016/J.IPL.2011.09.007
description: scientific article; zbMATH DE number 6150501