Weighted and Unweighted Maximum Clique Algorithms with Upper Bounds from Fractional Coloring

Abstract

The linear programming relaxation of the minimum vertex coloring problem, called the fractional coloring problem, is NP-hard. We describe efficient approximation procedures for both the weighted and unweighted versions of the problem. These fractional coloring procedures are then used for generating upper bounds for the (weighted or unweighted) maximum clique problem in the framework of a branch and bound procedure. Extensive computational testing shows that replacing the standard upper bounding procedures based on various integer coloring heuristics with the somewhat more expensive fractional coloring procedure results in improvements of the bound by up to one fourth in the unweighted and up to one fifth in the weighted case, accompanied by a decrease in the size of the search tree by a factor of almost two.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1993
Accession Number
ADA275328

Entities

People

  • Egon Balas
  • Jue Xue

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Air Platforms
  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Computers
  • Contracts
  • Coverings
  • Iterations
  • Linear Programming
  • Military Research
  • Probability
  • Residuals
  • Schools
  • Trees (Data Structures)
  • Universities

Fields of Study

  • Mathematics

Readers

  • Operations Research
  • Regression Analysis.