The problem of finding the minimum feedback vertex set in a graph is NP-coinplete, Two new heuristics for solving this problem are discussed. The first algorithm takes aclyaittoga of a fact that we prove—that if the graph has a polynomial number of cycles, they can be enumerated in polynomial time. A second heuristic is presented to solve the problem in general graphs. The algorithms' performance is shown to compare favorably to previously reported methods.
展开▼
