On the complexity of approximating the Hadwiger number
(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:
https://lup.lub.lu.se/record/1370600
- author
- Wahlén, Martin LU
- organization
- publishing date
- 2009
- 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}}, }