Heuristic algorithms with reasonable running time

本研究从实际应用的角度出发，得到了运行时间合理的启发式算法。我们处理了两个图划分问题，称为电源问题和均匀划分问题。对于电源问题，我们给出了一个近似算法，称为FPTAS。在此基础上，给出了一种启发式算法。对于一致划分问题，我们给出了一个求树的最优解的多项式时间算法。

In this research, we obtained heuristic algorithms which runs in reasonable time from the viewpoint of practical applications. We dealt with two graph partition problems, called the power-supply problem and the uniform partition problem. For the power-supply problem, we gave an approximation algorithm, called an FPTAS. Based on the FPTAS, we also gave a heuristic algorithm. For the uniform partition problem, we gave a polynomial-time algorithm which finds an optimal solution for trees.