Premium
Edge‐maximal triangulated subgraphs and heuristics for the maximum clique problem
Author(s) -
Xue Jue
Publication year - 1994
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230240208
Subject(s) - heuristics , clique , induced subgraph isomorphism problem , heuristic , clique problem , mathematics , combinatorics , enhanced data rates for gsm evolution , subgraph isomorphism problem , graph , clique graph , algorithm , computer science , mathematical optimization , theoretical computer science , line graph , artificial intelligence , pathwidth , voltage graph
In this paper, we present a polynomial algorithm that finds an edge‐maximal triangulated subgraph of an arbitrary graph. Then, we use this algorithm as a heuristic for the maximum (weight) clique problem. Finally, a local search routine is incorporated into our heuristic. Computational results comparing our algorithm with two existing edge‐maximal triangulated subgraph algorithms in the literature show that the subgraphs found by our algorithm tend to contain more edges as well as a better clique of the original graph. Computational results comparing our heuristic with other heuristics, including an efficient randomized heuristic, also show the promise of our heuristic. © 1994 by John Wiley & Sons, Inc.