Solving the stable set problem in terms of the odd cycle packing number

DOI10.4230/LIPIcs.FSTTCS.2014.187zbMath1360.68496OpenAlexW1493082098MaRDI QIDQ2978512

Andres J. Ruiz-Vargas, Yuri Faenza, Carsten Moldenhauer, Adrian Bock

Publication date: 25 April 2017

Full work available at URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2014.187

zbMATH Keywords

approximation algorithmsindependent set problemstable set problemmaximum subdeterminantsodd cycle packing number

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)

Related Items (6)

On lattice point counting in \(\varDelta\)-modular polyhedra ⋮ Induced odd cycle packing number, independent sets, and chromatic number ⋮ FPT-algorithms for some problems related to integer programming ⋮ A new contraction technique with applications to congruency-constrained cuts ⋮ Unnamed Item ⋮ An FPTAS for the \(\varDelta \)-modular multidimensional knapsack problem

This page was built for publication: Solving the stable set problem in terms of the odd cycle packing number