Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

On the complexity of approximating the Hadwiger number

Wahlén, Martin LU (2009) In Theoretical Computer Science 410(8-10). p.994-1000
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.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Approximation, Graph minors, Hadwiger number
in
Theoretical Computer Science
volume
410
issue
8-10
pages
994 - 1000
publisher
Elsevier
external identifiers
  • wos:000263945000037
  • scopus:59049084837
ISSN
0304-3975
DOI
10.1016/j.tcs.2008.12.020
language
English
LU publication?
yes
id
b1c7418c-bdd9-4ede-a78f-9af473b82c62 (old id 1370600)
date added to LUP
2016-04-01 14:54:43
date last changed
2022-04-22 05:52:41
@article{b1c7418c-bdd9-4ede-a78f-9af473b82c62,
  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.}},
  author       = {{Wahlén, Martin}},
  issn         = {{0304-3975}},
  keywords     = {{Approximation; Graph minors; Hadwiger number}},
  language     = {{eng}},
  number       = {{8-10}},
  pages        = {{994--1000}},
  publisher    = {{Elsevier}},
  series       = {{Theoretical Computer Science}},
  title        = {{On the complexity of approximating the Hadwiger number}},
  url          = {{http://dx.doi.org/10.1016/j.tcs.2008.12.020}},
  doi          = {{10.1016/j.tcs.2008.12.020}},
  volume       = {{410}},
  year         = {{2009}},
}