A simple modified version of Edmonds´ Branching algorithm for Minimum Weight Rooted Arborescence problem

Author

Xiaowei, Sun

Author_Institution

Software Coll., Shenyang Normal Univ., Shenyang

Volume

1

fYear

2008

fDate

12-15 Oct. 2008

Firstpage

1311

Lastpage

1315

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;

fLanguage

English

Publisher

ieee

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

Type

conf

DOI

10.1109/SOLI.2008.4686603

Filename

4686603