Approximation algorithms for clique transversals on some graph classes
DOI10.1016/J.IPL.2015.04.003zbMATH Open1329.68293OpenAlexW1976806052MaRDI QIDQ2346555FDOQ2346555
Authors: 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
Recommendations
- scientific article; zbMATH DE number 2044919
- Approximability of clique transversal in perfect graphs
- Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs
- LP Approaches to Improved Approximation for Clique Transversal in Perfect Graphs
- Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal
Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Covering all cliques of a graph
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
- Dominating sets for split and bipartite graphs
- Distance-hereditary graphs are clique-perfect
- Arboricity and Subgraph Listing Algorithms
- Covering the cliques of a graph with vertices
- 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
- Algorithmic Aspects of Neighborhood Numbers
- Algorithms for finding clique-transversals of graphs
Cited In (9)
- Algorithmic aspects of clique-transversal and clique-independent sets
- Optimal‐size clique transversals in chordal graphs
- Approximability of clique transversal in perfect graphs
- The algorithmic complexity of the minus clique-transversal problem
- Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal
- Upper Clique Transversals in Graphs
- LP Approaches to Improved Approximation for Clique Transversal in Perfect Graphs
- Algorithms for finding clique-transversals of graphs
- Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs
This page was built for publication: Approximation algorithms for clique transversals on some graph classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2346555)
