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.%グラフの最大誘導木抽出問題（以下，MAXIT）とは、「与えられたグラフにおける誘導部分グラフが木となる頂点集合のうちで，点数最大なものを求めよ．」と定義される．この間題はNP 困難であることが知られており，発見的解法が既にいくつか提案されている．本稿では，その中で比較的高速な隣接点付加に基づく解法に着目する．隣接点の選択ルールを種々改善することによって解の高精度化を図り，計算機実験によってそれらの効果を検証する．