Nordic Journal of Computing Bibliography

M. M. Halldórsson and J. Radhakrishnan. Improved approximations of independent sets in bounded-degree graphs via subgraph removal. Nordic Journal of Computing, 1(4):475-492, Winter 1994.
Abstract

Finding maximum independent sets in graphs with bounded maximum degree Delta is a well-studied NP-complete problem. We introduce an algorithm schema for improving the approximation of algorithms for this problem, which is based on preprocessing the input by removing cliques.

We give an implementation of a theorem on the independence number of clique-free graphs, and use it to obtain an O(Delta/loglog Delta) performance ratio with our schema. This is the first o(Delta) ratio for the independent set problem. We also obtain an efficient method with a Delta/6 (1 + o(1)) performance ratio, improving on the best performance ratio known for intermediate values of Delta.

Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.2 [Discrete Mathematics]: Graph Theory

Additional Key Words and Phrases: analysis of algorithms, approximation algorithms, independent sets

Selected papers that cite this one

Selected references


Shortcuts:

  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database