Greedy approximations of independent sets in low degree graphs

DOI10.1007/BFB0015418zbMath1512.68225MaRDI QIDQ6487957

Unnamed Author, Magnús M. Halldórsson

Publication date: 21 March 2023

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (4)

Using fractional primal-dual to schedule split intervals with demands ⋮ An efficient local search algorithm with large neighborhoods for the maximum weighted independent set problem† ⋮ Approximability results for stable marriage problems with ties. ⋮ Some APX-completeness results for cubic graphs

Cites Work

• Efficient bounds for the stable set, vertex cover and set packing problems
• Unnamed Item
• Unnamed Item

This page was built for publication: Greedy approximations of independent sets in low degree graphs