The maximum subforest problem: Approximation and exact algorithms Academic Article uri icon

abstract

  • Abstract We study the maximum subforest problem: Given a tree G and a set of trees H, find a subgraph G of G such that G does not contain a subtree isomorphic to a tree from H, and the number of edges in G is maximum. We give a polynomial time approximation scheme for this problem. We also give an exact algorithm for this problem whose time complexity is 2O (k2/log k) n, where n is the number of vertices in G, and k is the total number of vertices in H.

publication date

  • January 25, 1998