On the complexity of approximating the Hadwiger number

Martin Wahlén

    Research output: Contribution to journalArticlepeer-review

    3 Citations (SciVal)

    Abstract

    Unless P = NP there is no polynomial time approximation scheme (PTAS) for the problem of finding, for a graph G, the largest h such that the complete graph K-h is a minor of G. (C) 2008 Elsevier B.V. All rights reserved.
    Original languageEnglish
    Pages (from-to)994-1000
    JournalTheoretical Computer Science
    Volume410
    Issue number8-10
    DOIs
    Publication statusPublished - 2009

    Subject classification (UKÄ)

    • Computer Science

    Keywords

    • Approximation
    • Graph minors
    • Hadwiger number

    Fingerprint

    Dive into the research topics of 'On the complexity of approximating the Hadwiger number'. Together they form a unique fingerprint.

    Cite this