Approximability of clique transversal in perfect graphs
From MaRDI portal
Publication:724231
DOI10.1007/s00453-017-0315-3zbMath1392.68201OpenAlexW2613878116MaRDI QIDQ724231
N. S. Narayanaswamy, R. Krithika, Venkatesh Raman, Samuel Fiorini
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
Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Perfect graphs (05C17)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding odd cycle transversals.
- On the hardness of approximating minimum vertex cover
- The strong perfect graph theorem
- Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph
- A kernelization algorithm for \(d\)-hitting set
- The node-deletion problem for hereditary properties is NP-complete
- Geometric algorithms and combinatorial optimization
- The sandwich theorem
- On the existence of subexponential parameterized algorithms
- Algorithmic graph theory and perfect graphs
- Another disjoint compression algorithm for odd cycle transversal
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Recognizing Berge graphs
- Normal hypergraphs and the perfect graph conjecture
- Half-integrality, LP-branching, and FPT Algorithms
- The Design of Approximation Algorithms
- Kernels: Annotated, Proper and Induced
- Vertex packings: Structural properties and algorithms
- Properties of vertex packing and independence system polyhedra
- Parameterized Algorithms for (r,l)-Partization
- Faster Parameterized Algorithms Using Linear Programming
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
- Parameterized Algorithms
- On the complexity of \(k\)-SAT
