有向图最多叶子生成树问题研究

为求解有向图最多叶子生成树(出分枝)问题,提出了一些规约规则,对有向图实施这些规约规则能降低原图的规模;随后设计了近似算法在规约后的图中求解指定根节点的最多叶子出分枝问题。对于用近似算法求得的出分枝,又结合前面的规约规则设计了优化规则,以进一步通过优化变换增加出分枝的叶子节点。仿真实验表明,规约规则、近似算法和优化规则是有效的。

Study of directed maximum leaf out-branching

In order to solve the problem of maximum leaf spanning tree in digraph,some reduction rules were proposed.These reduction rules could reduce the size of original digraph efficiently.An approximation algorithm was given to find an out-branching with many leaves in the reduced digraph.Furthermore,some optimization rules were given to improve the out-branching.The simulation results show that the reduction rules,approximation algorithm,and optimization rules are effective.