Approximability of clique transversal in perfect graphs

DOI10.1007/S00453-017-0315-3zbMATH Open1392.68201OpenAlexW2613878116MaRDI QIDQ724231FDOQ724231

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

Publication date: 25 July 2018

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-017-0315-3

Recommendations

• LP Approaches to Improved Approximation for Clique Transversal in Perfect Graphs
• Approximation algorithms for clique transversals on some graph classes
• On clique-transversals and clique-independent sets
• Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal
• Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs

zbMATH Keywords

linear programmingapproximation algorithmsperfect graphsodd cycle transversalr-clique transversal

Mathematics Subject Classification ID

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

Cites Work

• The design of approximation algorithms
• Geometric algorithms and combinatorial optimization
• Normal hypergraphs and the perfect graph conjecture
• Approximation algorithms for NP-hard problems.
• Kernels: Annotated, Proper and Induced
• Properties of vertex packing and independence system polyhedra
• Finding odd cycle transversals.
• A kernelization algorithm for \(d\)-hitting set
• The node-deletion problem for hereditary properties is NP-complete
• Algorithmic graph theory and perfect graphs
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Half-integrality, LP-branching, and FPT algorithms
• Parameterized algorithms
• On the complexity of \(k\)-SAT
• On the hardness of approximating minimum vertex cover
• The strong perfect graph theorem
• Recognizing Berge graphs
• Vertex packings: Structural properties and algorithms
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• On the existence of subexponential parameterized algorithms
• The sandwich theorem
• Title not available (Why is that?)
• Faster parameterized algorithms using linear programming
• Another disjoint compression algorithm for odd cycle transversal
• Title not available (Why is that?)
• Parameterized algorithms for \((r,l)\)-partization
• Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph

Cited In (7)

• Optimal‐size clique transversals in chordal graphs
• Computing the clique number of \(a\)-perfect graphs in polynomial time
• Approximation algorithms for clique transversals on some graph classes
• The algorithmic complexity of the minus clique-transversal problem
• Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal
• Reconfiguration of colorable sets in classes of perfect graphs
• LP Approaches to Improved Approximation for Clique Transversal in Perfect Graphs

This page was built for publication: Approximability of clique transversal in perfect graphs

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