On Graphs with Polynomially Solvable Maximum-Weight Clique Problem
Journal
Networks
Journal Volume
19
Journal Issue
2
Pages
247-253
Date Issued
1989-01
Author(s)
Abstract
Abstract We give 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 we then identify a family of graphs with polynomially solvable maximum weight clique problem, using the edgebicoloring approach developed in a recent paper by Balas, Chvatal, and Nesetril.
Type
journal article