MODELAGEM E OTIMIZAÇÃO DE FLUXO EM UMA REDE REAL CONECTADA
DOI:
https://doi.org/10.20873/uft.2359-3652.2016v3nespp99Keywords:
Fluxo máximo, Otimização de Sistemas, Teoria dos grafosAbstract
In this work, we approached the maximum flow problem from the graph theory perspective with the goal of providing a software implementation of an algorithmic solution to the problem for later use in optimization of network design and IP routing. Initially, we bring context and definition to the problem. Next, we present the studied algorithms, the methodology and the executed experiments. We coded two solutions to this problem from the literature: The Ford-Fulkerson algorithm and the Edmonds-Karp algorithm. A system in the form of a fiber optic network was modeled as a graph and the algorithms were applied to the model as proof of concept. Additionally, to empirically evaluate the algorithms’ correctness and performance, we made a random graph base with varying sizes and edge densities and ran the algorithms on those. The comparison of the results show that the Edmonds-Karp algorithm has greater performance.
References
CORMEN, T.H.; LEISERSON, C.E.; RIVEST, R.L.; STEIN, C. Introduction to Algorithms (3 ed.), Capítulo 26. MIT Press, 2009.
EDMONDS, J.; KARP, R.M. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the Association for Computing Machinery, Vol. 19, No. 2, 1972.
FORD, L. R.; FULKERSON, D. R. "Maximal flow through a network". Canadian Journal of Mathematics, Vol 8, 1956.
GOODAIRE, E. G.; PARMENTER, M. M.
Discrete Mathematics with Graph Theory. Prentice-Hall, 1997.
LEVITIN, A. V. Introduction to the Design and Analysis of Algorithms (3 ed), Pearson; 2011.
Downloads
Published
How to Cite
Issue
Section
License
Autores que publicam nesta revista concordam com os seguintes termos:
1. Autores mantém os direitos autorais e concedem à revista o direito de primeira publicação, com o trabalho simultaneamente licenciado sob a Creative Commons Attribution License (CC BY-NC 4.0), permitindo o compartilhamento do trabalho com reconhecimento da autoria do trabalho e publicação inicial nesta revista.
2. Autores têm autorização para assumir contratos adicionais separadamente, para distribuição não-exclusiva da versão do trabalho publicada nesta revista (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento de autoria e publicação inicial nesta revista.
3. Autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) a qualquer ponto posterior ao processo editorial.
4. Além disso, o AUTOR é informado e consente com a revista que, portanto, seu artigo pode ser incorporado pela DESAFIOS em bases e sistemas de informação científica existentes (indexadores e bancos de dados atuais) ou a existir no futuro (indexadores e bancos de dados futuros), nas condições definidas por este último em todos os momentos, que envolverá, pelo menos, a possibilidade de que os titulares desses bancos de dados possam executar as seguintes ações sobre o artigo:
a. Reproduzir, transmitir e distribuir o artigo, no todo ou em parte sob qualquer forma ou meio de transmissão eletrônica existente ou desenvolvida no futuro, incluindo a transmissão eletrônica para fins de pesquisa, visualização e impressão;
b. Reproduzir e distribuir, no todo ou em parte, o artigo na impressão.
c. Capacidade de traduzir certas partes do artigo.
d. Extrair figuras, tabelas, ilustrações e outros objetos gráficos e capturar metadados, legendas e artigo relacionado para fins de pesquisa, visualização e impressão.
e. Transmissão, distribuição e reprodução por agentes ou autorizada pelos proprietários de distribuidoras de bases de dados.
f. A preparação de citações bibliográficas, sumários e índices e referências de captura relacionados de partes selecionadas do artigo.
g. Digitalizar e / ou armazenar imagens e texto de artigo eletrônico.
