Title :
A simple modified version of Edmonds´ Branching algorithm for Minimum Weight Rooted Arborescence problem
Author_Institution :
Software Coll., Shenyang Normal Univ., Shenyang
Abstract :
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.
Keywords :
computational complexity; directed graphs; optimisation; trees (mathematics); Edmond branching algorithm generalization; complexity analysis; directed graph; minimum weight rooted arborescence problem; optimization problem; spanning tree; Circuits; Educational institutions; Linear programming; Publishing; Software algorithms; Terminology; Tree graphs; acyclic digraph; algorithm and complexity; arborescence; minimum weight; rooted;
Conference_Titel :
Service Operations and Logistics, and Informatics, 2008. IEEE/SOLI 2008. IEEE International Conference on
Conference_Location :
Beijing
Print_ISBN :
978-1-4244-2012-4
Electronic_ISBN :
978-1-4244-2013-1
DOI :
10.1109/SOLI.2008.4686603
