2022-08-11T21:41:53Zhttps://nagoya.repo.nii.ac.jp/oaioai:nagoya.repo.nii.ac.jp:000131712021-03-01T18:36:49ZInapproximability of the Edge-Contraction ProblemOTSUKI, HideakiHIRATA, TomioCopyright (C) 2006 IEICEedge-contraction problemNP-hardapproximation algorithmapproximabilityconnected vertex cover problemFor 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.Institute of Electronics, Information and Communication Engineers2006-05-01engjournal articlehttp://hdl.handle.net/2237/15066https://nagoya.repo.nii.ac.jp/records/131710916-8508IEICE transactions on fundamentals of electronics, communications and computer sciencesE89-A514251427https://nagoya.repo.nii.ac.jp/record/13171/files/465.pdfapplication/pdf106.3 kB2018-02-20