On the Maximum-Weight Clique Problem.

Abstract

The authors introduce several new classes of graphs on which the maximum-weight clique problem is solvable in polynomial time. Their common feature, and the central idea of their algorithms, is that every clique of and of these graphs is contained in some member of a polynomial-sized collection of induced subgraphs that are complements of bipartite graphs. Their approach is quite general, and might conceivably yield many other classes of graphs along with corresponding polynomial time algorithms. Additional keywords: Triangulated graphs; Triangle free graphs; Theorems. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1985
Accession Number
ADA159953

Entities

People

  • E. Balas
  • J. Nesetril
  • V. Chvatal

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Computer Programming
  • Graph Theory
  • Inequalities
  • Linear Programming
  • Mathematics
  • Military Research
  • New York
  • Observation
  • Polynomials
  • Probability
  • Random Variables
  • Triangles
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.