Hard graphs for the maximum clique problem

C. Hoede

doi:10.1016/0012-365X(88)90207-5

Hard graphs for the maximum clique problem

C. Hoede

Research output: Contribution to journal › Article › Academic

7 Citations (Scopus)

597 Downloads (Pure)

Abstract

The maximum clique problem is one of the NP-complete problems. There are graphs for which a reduction technique exists that transforms the problem for these graphs into one for graphs with specific properties in polynomial time. The resulting graphs do not grow exponentially in order and number. Graphs that allow such a reduction technique are called soft. Hard graphs are those graphs for which none of the reduction techniques can be applied. A list of properties of hard graphs is determined.

Original language	Undefined
Pages (from-to)	175-179
Journal	Discrete mathematics
Volume	72
Issue number	1-3
DOIs	https://doi.org/10.1016/0012-365X(88)90207-5
Publication status	Published - 1988

Keywords

IR-70038

Access to Document

10.1016/0012-365X(88)90207-5

Hoede88hardFinal published version, 267 KB

Cite this

@article{44766cf7d80b4084a95ffb745c61ae1e,

title = "Hard graphs for the maximum clique problem",

abstract = "The maximum clique problem is one of the NP-complete problems. There are graphs for which a reduction technique exists that transforms the problem for these graphs into one for graphs with specific properties in polynomial time. The resulting graphs do not grow exponentially in order and number. Graphs that allow such a reduction technique are called soft. Hard graphs are those graphs for which none of the reduction techniques can be applied. A list of properties of hard graphs is determined.",

keywords = "IR-70038",

author = "C. Hoede",

year = "1988",

doi = "10.1016/0012-365X(88)90207-5",

language = "Undefined",

volume = "72",

pages = "175--179",

journal = "Discrete mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "1-3",

}

TY - JOUR

T1 - Hard graphs for the maximum clique problem

AU - Hoede, C.

PY - 1988

Y1 - 1988

N2 - The maximum clique problem is one of the NP-complete problems. There are graphs for which a reduction technique exists that transforms the problem for these graphs into one for graphs with specific properties in polynomial time. The resulting graphs do not grow exponentially in order and number. Graphs that allow such a reduction technique are called soft. Hard graphs are those graphs for which none of the reduction techniques can be applied. A list of properties of hard graphs is determined.

AB - The maximum clique problem is one of the NP-complete problems. There are graphs for which a reduction technique exists that transforms the problem for these graphs into one for graphs with specific properties in polynomial time. The resulting graphs do not grow exponentially in order and number. Graphs that allow such a reduction technique are called soft. Hard graphs are those graphs for which none of the reduction techniques can be applied. A list of properties of hard graphs is determined.

KW - IR-70038

U2 - 10.1016/0012-365X(88)90207-5

DO - 10.1016/0012-365X(88)90207-5

M3 - Article

SN - 0012-365X

VL - 72

SP - 175

EP - 179

JO - Discrete mathematics

JF - Discrete mathematics

IS - 1-3

ER -