Um Algoritmo para o Problema da Árvore Geradora Mínima com Estrutura Incerta (An Algorithm for the Minimum Spanning Tree Problem with Uncertain Structures)

Fábio Hernandes (, Matheus Lourenço (

1Universidade Estadual do Centro-Oeste, UNICENTRO-PR

This paper appears in: Revista IEEE América Latina

Publication Date: Dec. 2015
Volume: 13,   Issue: 12 
ISSN: 1548-0992

The minimum spanning tree problem consists to find the smallest weight among all possible trees in a network. It is one of the main problems of graphs theory, since it has a wide range of applications in Engineering and Computation areas, such as: electricity distribution networks, information storage, transportation, etc. In this paper is proposed an exact algorithm to the minimum spanning tree problem with uncertain structures. It is based on the mainly papers of the literature and presents a solution ordered set of minimum spanning trees. The uncertainties of the structures are resolved using the fuzzy sets theory. The algorithm was tested on literature instances having the same results. Its complexity is O((v-a)(v^2)), where v is the node sets and a is the arcs sets.

Index Terms:
Graphs Theory, Spanning Tree Problem, Prim Algorithm, Fuzzy Sets Theory.   

Documents that cite this document
This function is not implemented yet.

[PDF Full-Text (323)]