Inapproximability of the Edge-Contraction Problem

Hideaki OTSUKI; Tomio HIRATA

doi:10.1093/ietfec/e89-a.5.1425

Copy

Hideaki OTSUKI, Tomio HIRATA, "Inapproximability of the Edge-Contraction Problem" in IEICE TRANSACTIONS on Fundamentals, vol. E89-A, no. 5, pp. 1425-1427, May 2006, doi: 10.1093/ietfec/e89-a.5.1425.
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e89-a.5.1425/_p

Copy

@ARTICLE{e89-a_5_1425,
author={Hideaki OTSUKI, Tomio HIRATA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Inapproximability of the Edge-Contraction Problem},
year={2006},
volume={E89-A},
number={5},
pages={1425-1427},
abstract={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.},
keywords={},
doi={10.1093/ietfec/e89-a.5.1425},
ISSN={1745-1337},
month={May},}

Copy

TY - JOUR
TI - Inapproximability of the Edge-Contraction Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1425
EP - 1427
AU - Hideaki OTSUKI
AU - Tomio HIRATA
PY - 2006
DO - 10.1093/ietfec/e89-a.5.1425
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E89-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2006
AB - 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.
ER -