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

Study of directed maximum leaf out-branching

作　　者：高文宇[1] 

机构地区：[1]广东商学院信息学院,广州510320

出　　处：《计算机应用》2010年第6期1431-1433,1438,共4页journal of Computer Applications

基　　金：广东省自然科学基金资助项目(8151032001000013)

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

关 键 词：最多叶子生成树 出分枝 有向图 规约 近似算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]