Computing Experiment-based Evaluation of Heuristic Algorithms for Extracting a Maximum Induced Tree of 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 these algorithms are useful tools for solving the constrained via minimization problems for layout design of printed wiring boards. The subjects of the paper are the following (1) and (2). (1) Several heuristic algorithms for MAXIT are proposed and (2) their capability is compared through computing experiment.