On the removal of forbidden graphs by edge-deletion or by edge-contraction |
| |
Authors: | Toshimasa Watanabe Tadashi Ae Akira Nakamura |
| |
Institution: | Faculty of Engineering, Hiroshima University, Hiroshima 730, Japan |
| |
Abstract: | If π is a property on graphs, the corresponding edge deletion (edge contraction, respectively) problem is: Given a graph G, determine the minimum number of edges of G whose deletion (contraction) results in a graph satisfying property π. We show that these problems are NP-hard if π is finitely characterizable by 3-connected graphs. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|