A Simple Modified Version of Edmonds Branching Algorithm for Minimum Weight Rooted Arborescence Problem

摘要：

We consider a general optimization problem regarding spanning trees in directed graphs (arborescence).We present an algorithm for solving such problem,which can be considered as a generalization of Edmonds Branching algorithm for the solution of the Minimum Weight Rooted Arborescence (MWRA) problem.This paper studies the problem of finding a minimum weight rooted arborescence in a rooted digraph with weights on edges.A method is developed for this problem,and computational results are reported.

关键词： arborescence rooted minimum weight acyclic digraph algorithm and complexity

作者: Sun Xiaowei

作者单位: IEEE Conference Publishing Software College,Shenyang Normal University Shenyang 110034 China

会议类型: 国际会议

会议名称: 2008 IEEE International Conference on Service Operations and Logistics, and Informatics(IEEE/SOLI’2008)(IEEE服务运作、物流与信息年会)

会议地点: 北京

会议语种:英文

在线出版日期: 2008-10-12（万方平台首次上网日期，不代表论文的发表时间）