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

• 作者: 高文宇
• 来源期刊: 计算机应用
• 学科: 工学
• 关键词: 最多叶子生成树 出分枝 有向图 规约 近似算法
• 年，卷（期）: 2010,（6）
• 所属期刊栏目: 网络与通信
• 页码范围: 1431-1433,1438
• 分类号: TP301.6
• 字数: 4385字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	高文宇	广东商学院信息学院	19	173	7.0	12.0