More on Graphs with Polynomially Solvable Maximum-Weight Clique Problem.
Abstract
This document gives a new bound on the number of maximal cliques in a graph along with a bound on the length of odd antiholes that the graph can contain. Based on these bounds a family of graphs with polynomially solvable maximum weight clique problem is identified using the edge-bicoloring approach developed in a a recent paper by Balas, Chvatal and Nesetril. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1986
- Accession Number
- ADA177222
Entities
People
- Chang S. Yu
- Egon Balas
Organizations
- Carnegie Mellon University