Minimum Spanning Tree
Mostrando 1-12 de 22 artigos, teses e dissertações.
-
1. k-árvores de custo mínimo / Minimum cost k-trees
Esta dissertação trata do problema da k-árvore de custo mínimo (kMST): dados um grafo conexo G, um custo não-negativo c_e para cada aresta e e um número inteiro positivo k, encontrar uma árvore com k vértices que tenha custo mínimo. O kMST é um problema NP-difícil e portanto não se conhece um algoritmo polinomial para resolvê-lo. Nesta disserta�
IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia. Publicado em: 11/06/2010
-
2. Estruturas de dados eficientes para algoritmos evolutivos aplicados a projeto de redes / Efficient Data Structures to Evolutionary Algorithms Applied to Network Design Problems.
Network design problems (NDPs) are very important since they involve several applications from areas of Engineering and Sciences. In order to solve the limitations of traditional algorithms for NDPs that involve real world complex networks (in general, modeled by large-scale complete or sparse graphs), heuristics, such as evolutionary algorithms (EAs), have
Publicado em: 2009
-
3. DESENVOLVIMENTO DE METAHEURÍSTICAS PARA O PROBLEMA DA ÁRVORE GERADORA MÍNIMA GENERALIZADO
The generalized minimum spanning tree problem is present in several situations of the real world, such as in the context of the telecommunications, transports and grouping of data, where a net of necessary clusters to be connected using a node of each cluster. In that work it is presented the project and the implementation of an algorithm of tabu search with
Publicado em: 2008
-
4. AUTONOMIC PARALELIZATION OF METAHEURISTICS IN COMPUTATIONAL GRIDS / PARALELIZAÇÃO AUTONÔMICA DE METAHEURÍSTICAS EM AMBIENTES DE GRID
The development of autonomic parallel metaheuristics to be efficiently executed in computational grid is the challenge of this thesis. The parallel application must be able to self-adjust to the changes that occur dynamically in the environment, without the user needing to interfere directly in the code of the application. For this, the autonomic metaheurist
Publicado em: 2008
-
5. MODELS AND ALGORITHMS FOR THE DIAMETER CONSTRAINED MINIMUM SPANNING TREE PROBLEM / MODELOS E ALGORITMOS PARA O PROBLEMA DA ÁRVORE GERADORA DE CUSTO MÍNIMO COM RESTRIÇÃO DE DIÂMETRO
In this work, models and approximation algorithms to solve the Diameter Constrained Minimum Spanning Tree Problem (AGMD) are proposed. This problem typically models network design applications where all vertices must communicate with each other at a minimum cost, while meeting a given quality requirement. The formulations proposed by Achuthan and Caccetta ar
Publicado em: 2006
-
6. A Particle Swarm Approach for Combinatorial Optimization Problems / Uma abordagem por nuvem de partículas para problemas de otimização combinatória
Combinatorial optimization problems have the goal of maximize or minimize functions defined over a finite domain. Metaheuristics are methods designed to find good solutions in this finite domain, sometimes the optimum solution, using a subordinated heuristic, which is modeled for each particular problem. This work presents algorithms based on particle swarm
Publicado em: 2006
-
7. Computação evolutiva aplicada a resolução do problema da arvore geradora minima com parametros fuzzy / Evolutionary computation applied to solve the minimum spanning tree problem with fuzzy parameters
Este trabalho propoe meta-heurýsticas baseadas em tecnicas da computaçao evolutiva, que visam encontrar um conjunto de arvores geradoras mýnimas para problemas de grafos, que possuem incertezas em relaçao as informaçoes associadas aos parametros. Resolver problemas dessa natureza e um processo NP-Completo, pois envolve um numero enorme de comparaçoes.
Publicado em: 2006
-
8. An algorithm to generate all spanning trees of a graph in order of increasing cost
A minimum spanning tree of an undirected graph can be easily obtained using classical algorithms by Prim or Kruskal. A number of algorithms have been proposed to enumerate all spanning trees of an undirected graph. Good time and space complexities are the major concerns of these algorithms. Most algorithms generate spanning trees using some fundamental cut o
Pesquisa Operacional. Publicado em: 2005-08
-
9. Minimização de pedras em redes de distribuição de energia eletrica atraves de metodos de busca inteligentes com processamento paralelo
This thesis addresses the problem of loss minimization for electric energy distribution system. As distribution networks operates radially, the problem can be formulated as a generalization of minimum spanning tree problem. The minimum loss solution is obtained in two steps. The constraint of radial operation is relaxes in the first step, leading to an optim
Publicado em: 1999
-
10. Processamento distribuido aplicado a analise de segurança estatica de sistemas de energia eletrica
Este trabalho focaliza o problema de análise de contingências e as técnicas de cálculo do fluxo de potência ótimo com restrições de segurança. A abordagem do fluxo de potência ótimo está essencialmente voltada para o alívio de violações de limites de fluxos de potência ativa em ramos (sobrecargas) através de ações sobre os controles ativos
Publicado em: 1997
-
11. The Steiner ratio conjecture of Gilbert and Pollak is true.
Let P be a set of n points on the euclidean plane. Let Ls(P) and Lm(P) denote the lengths of the Steiner minimum tree and the minimum spanning tree on P, respectively. In 1968, Gilbert and Pollak conjectured that for any P, Ls(P) >/= (radical3/2)Lm(P). We provide an abridged proof for their conjecture in this paper.
-
12. Use of the Minimum Spanning Tree Model for Molecular Epidemiological Investigation of a Nosocomial Outbreak of Hepatitis C Virus Infection
The minimum spanning tree (MST) model was applied to identify the history of transmission of hepatitis C virus (HCV) infection in an outbreak involving five children attending a pediatric oncology-hematology outpatient ward between 1992 and 2000. We collected blood samples from all children attending since 1992, all household contacts, and one health care wo
American Society for Microbiology.