MSArbor.h File Reference

Solves the Minimal Spanning Arborescence problem, with a C++ implementation of the ARBOR algorithm [M.Fischetti and P.Toth, ORSA J.on Computing 5(4), 1993] for MSA on complete graphs. More...

Classes
class	MSArbor
	Given a (complete) directed graph G = ( N , A ), with n = |N| nodes and m = |A| (= n ( n - 1 )) arcs, and arc costs C[ i , j ], the Minimal Spanning Arborescence problem (MSA) with root r requires to find a directed spanning tree (arborescence) of G rooted in r with minimal total cost, where the cost is the sum of the costs of the arcs belonging to the tree. More...

Namespaces
	MSA_di_unipi_it
	The namespace MSA_di_unipi_it is defined to hold the MSArbor class.

Detailed Description

Solves the Minimal Spanning Arborescence problem, with a C++ implementation of the ARBOR algorithm [M.Fischetti and P.Toth, ORSA J.on Computing 5(4), 1993] for MSA on complete graphs.

Version

1.13

Date

01 - 09 - 2009

Author

Antonio Frangioni
Operations Research Group
Dipartimento di Informatica
Universita' di Pisa

Daniele Pretolani
Dipartimento di Matematica
Universita' di Camerino

Marisa Traini
Dipartimento di Matematica
Universita' di Camerino
Copyright &copy 2004 - 2009 A. Frangioni, D. Pretolani

This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA or check www.gnu.org.