On the complexity of approximating the Hadwiger number

Martin Wahlén

doi:10.1016/j.tcs.2008.12.020

On the complexity of approximating the Hadwiger number

Martin Wahlén

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

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 language	English
Pages (from-to)	994-1000
Journal	Theoretical Computer Science
Volume	410
Issue number	8-10
DOIs	https://doi.org/10.1016/j.tcs.2008.12.020
Publication status	Published - 2009

Subject classification (UKÄ)

Computer Science

Free keywords

Approximation
Graph minors
Hadwiger number

Access to Document

10.1016/j.tcs.2008.12.020

Cite this

@article{b1c7418cbdd94edea78f9af473b82c62,

title = "On the complexity of approximating the Hadwiger number",

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.",

keywords = "Approximation, Graph minors, Hadwiger number",

author = "Martin Wahl{\'e}n",

year = "2009",

doi = "10.1016/j.tcs.2008.12.020",

language = "English",

volume = "410",

pages = "994--1000",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

number = "8-10",

}

TY - JOUR

T1 - On the complexity of approximating the Hadwiger number

AU - Wahlén, Martin

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

KW - Approximation

KW - Graph minors

KW - Hadwiger number

U2 - 10.1016/j.tcs.2008.12.020

DO - 10.1016/j.tcs.2008.12.020

M3 - Article

SN - 0304-3975

VL - 410

SP - 994

EP - 1000

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 8-10

ER -

On the complexity of approximating the Hadwiger number

Abstract

Subject classification (UKÄ)

Free keywords

Access to Document

Fingerprint

Cite this