LP Approaches to Improved Approximation for Clique Transversal in Perfect Graphs

DOI10.1007/978-3-662-44777-2_36MaRDI QIDQ2921429zbMATH OpenOpenAlexFDO

Authors Samuel Fiorini, R. Krithika, N. S. Narayanaswamy, Venkatesh Raman

Publication date 8 October 2014

Published in Algorithms - ESA 2014 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-44777-2_36

Mathematics Subject Classification ID

Linear programming (90C05) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Perfect graphs (05C17)

Recommendations

• Approximability of clique transversal in perfect graphs
• Approximation algorithms for clique transversals on some graph classes
• Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal
• Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs
• Algorithms for finding clique-transversals of graphs
• Algorithmic aspects of the generalized clique-transversal problem on chordal graphs
• Optimal‐size clique transversals in chordal graphs
• Bounding clique-width via perfect graphs
• Bounding clique-width via perfect graphs
• On the approximability of clique and related maximization problems

Cited in

(6)

• Perfect LRCs and k-optimal LRCs
• Approximation algorithms for clique transversals on some graph classes
• Approximability of clique transversal in perfect graphs
• Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal
• Reconfiguration of Colorable Sets in Classes of Perfect Graphs
• An improved analysis for a greedy remote-clique algorithm using factor-revealing LPs

This page was built for publication: LP Approaches to Improved Approximation for Clique Transversal in Perfect Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2921429)