Hard graphs for the maximum clique problem

C. Hoede

    Research output: Contribution to journalArticleAcademic

    2 Citations (Scopus)
    105 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 languageUndefined
    Pages (from-to)175-179
    JournalDiscrete mathematics
    Volume72
    Issue number1-3
    DOIs
    Publication statusPublished - 1988

    Keywords

    • IR-70038

    Cite this