Sharp Heuristic Algorithms for Extracting a Maximum Induced Tree from a Graph

摘要

The problem of extracting a maximum induced tree of a graph (MAXIT), asks for a vertex set of largest cardinality among those ones each of which induces a tree of a given graph. It is known that this problem is NP-hard, and some heuristic algorithms have been proposed. The paper focuses on algorithms based on enlarging a tree, since they are relatively fast algorithms. The subjects of the paper are the following (1) and (2). (1) Improving selection rules for enlarging a tree so that their solution may be produced, for MAXIT; (2) Comparing their capability by computing experiment.