A FAST ALGORITHM FOR THE MAXIMUM WEIGHT CLIQUE PROBLEM

被引：41

作者：

BABEL, L

机构：

[1] Institut für Mathematik TU-München, München, D-80290

来源：

COMPUTING | 1994年 / 52卷 / 01期

关键词：

MAXIMUM CLIQUE FINDING; WEIGHTED PROBLEM; EXACT ALGORITHM;

D O I：

10.1007/BF02243394

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present a branch and bound method which finds a maximum weight clique in an arbitrary weighted graph. The main ingredients are a weighted coloring heuristic which simultaneously produces lower and upper bounds and a branching rule that uses the information obtained in the coloring. The algorithm performs comparable to the fastest method known so far but is much easier to implement.

引用

页码：31 / 38

页数：8

共 14 条

[1]

Babel L., 1990, ZOR, Methods and Models of Operations Research, V34, P207, DOI 10.1007/BF01415983

[2] FINDING MAXIMUM CLIQUES IN ARBITRARY AND IN SPECIAL GRAPHS [J].