Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00183 Finding Large Clique Minors is Hard David Eppstein Vol. 13, no. 2, pp. 197-204, 2009. Concise paper Abstract We prove that it is NP-complete, given a graph G and a parameter h, to determine whether G contains a complete graph Kh as a minor.
|
Revised: May 2009. Reviewed: April 2009. Final: July 2009. Published: July 2009. Accepted: July 2009. Submitted: June 2008. Communicated by Giuseppe Liotta |
Journal of Graph Algorithms and Applications |