@article{oai:nagoya.repo.nii.ac.jp:00013171,
author = {OTSUKI, Hideaki and HIRATA, Tomio},
issue = {5},
journal = {IEICE transactions on fundamentals of electronics, communications and computer sciences},
month = {May},
note = {For a property π on graphs, the edge-contraction problem with respect to π is defined as a problem of finding a set of edges of minimum cardinality whose contraction results in a graph satisfying the property π. This paper gives a lower bound for the approximation ratio for the problem for any property π that is hereditary on contractions and determined by biconnected components.},
pages = {1425--1427},
title = {Inapproximability of the Edge-Contraction Problem},
volume = {E89-A},
year = {2006}
}