Improved approximations of independent sets in bounded-degree graphs

DOI10.1007/3-540-58218-5_18zbMath1502.68229OpenAlexW1601088202MaRDI QIDQ5054761

Magnús M. Halldórsson, Jaikumar Radhakrishnan

Publication date: 9 December 2022

Published in: Algorithm Theory — SWAT '94 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-58218-5_18

zbMATH Keywords

local searchindependence numberperformance ratiomaximum degreefree graph

Mathematics Subject Classification ID

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

Related Items (1)

On approximation properties of the Independent set problem for degree 3 graphs

Cites Work

• Unnamed Item
• Unnamed Item
• A note on the independence number of triangle-free graphs
• Efficient bounds for the stable set, vertex cover and set packing problems
• A note on Ramsey numbers
• On Turan's theorem for sparse graphs
• Optimization, approximation, and complexity classes
• Approximating maximum independent sets by excluding subgraphs
• Improved non-approximability results
• Greed is good
• On Syntactic versus Computational Views of Approximability

This page was built for publication: Improved approximations of independent sets in bounded-degree graphs