An algorithm for finding a maximum clique in a graph

David R. Wood

doi:10.1016/S0167-6377(97)00054-0

An algorithm for finding a maximum clique in a graph

David R. Wood

Research output: Contribution to journal › Article › Research › peer-review

95 Citations (Scopus)

Abstract

This paper introduces a branch-and-bound algorithm for the maximum clique problem which applies existing clique finding and vertex coloring heuristics to determine lower and upper bounds for the size of a maximum clique. Computational results on a variety of graphs indicate the proposed procedure in most instances outperforms leading algorithms.

Original language	English
Pages (from-to)	211-217
Number of pages	7
Journal	Operations Research Letters
Volume	21
Issue number	5
DOIs	https://doi.org/10.1016/S0167-6377(97)00054-0
Publication status	Published - 12 Jan 1997

Keywords

Branch-and-bound algorithm
Fractional coloring
Graph algorithm
Maximum clique problem
Vertex coloring

Access to Document

10.1016/S0167-6377(97)00054-0

Cite this

@article{595d3b5b46bf4ac5b634d79f939b2f0c,

title = "An algorithm for finding a maximum clique in a graph",

abstract = "This paper introduces a branch-and-bound algorithm for the maximum clique problem which applies existing clique finding and vertex coloring heuristics to determine lower and upper bounds for the size of a maximum clique. Computational results on a variety of graphs indicate the proposed procedure in most instances outperforms leading algorithms.",

keywords = "Branch-and-bound algorithm, Fractional coloring, Graph algorithm, Maximum clique problem, Vertex coloring",

author = "Wood, {David R.}",

year = "1997",

month = jan,

day = "12",

doi = "10.1016/S0167-6377(97)00054-0",

language = "English",

volume = "21",

pages = "211--217",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "5",

}

TY - JOUR

T1 - An algorithm for finding a maximum clique in a graph

AU - Wood, David R.

PY - 1997/1/12

Y1 - 1997/1/12

N2 - This paper introduces a branch-and-bound algorithm for the maximum clique problem which applies existing clique finding and vertex coloring heuristics to determine lower and upper bounds for the size of a maximum clique. Computational results on a variety of graphs indicate the proposed procedure in most instances outperforms leading algorithms.

AB - This paper introduces a branch-and-bound algorithm for the maximum clique problem which applies existing clique finding and vertex coloring heuristics to determine lower and upper bounds for the size of a maximum clique. Computational results on a variety of graphs indicate the proposed procedure in most instances outperforms leading algorithms.

KW - Branch-and-bound algorithm

KW - Fractional coloring

KW - Graph algorithm

KW - Maximum clique problem

KW - Vertex coloring

UR - http://www.scopus.com/inward/record.url?scp=0031379277&partnerID=8YFLogxK

U2 - 10.1016/S0167-6377(97)00054-0

DO - 10.1016/S0167-6377(97)00054-0

M3 - Article

SN - 0167-6377

VL - 21

SP - 211

EP - 217

JO - Operations Research Letters

JF - Operations Research Letters

IS - 5

ER -

An algorithm for finding a maximum clique in a graph

Abstract

Keywords

Access to Document

Other files and links

Cite this