Accession Number:

ADA159953

Title:

On the Maximum-Weight Clique Problem.

Descriptive Note:

Management science research rept.,

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s):

Report Date:

1985-06-01

Pagination or Media Count:

30.0

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

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE