Approximation algorithms for clique transversals on some graph classes

DOI10.1016/j.ipl.2015.04.003zbMath1329.68293OpenAlexW1976806052MaRDI QIDQ2346555

Min Chih Lin, Saveliy Vasiliev

Publication date: 2 June 2015

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

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

zbMATH Keywords

NP-hardapproximation algorithmsgraph classesclique transversal

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Cites Work

• Dominating sets for split and bipartite graphs
• Algorithms for finding clique-transversals of graphs
• Covering all cliques of a graph
• Covering the cliques of a graph with vertices
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On clique-transversals and clique-independent sets
• Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs
• Algorithmic aspects of clique-transversal and clique-independent sets
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Distance-hereditary graphs are clique-perfect
• Arboricity and Subgraph Listing Algorithms
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Algorithmic Aspects of Neighborhood Numbers

This page was built for publication: Approximation algorithms for clique transversals on some graph classes