有向图最多叶子生成树问题研究 (2010年)

【文件属性】：

文件名称：有向图最多叶子生成树问题研究 (2010年)

文件大小：349KB

文件格式：PDF

更新时间：2024-06-05 02:41:40

工程技术 论文

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