Título: | ALGORITHMS FOR PERFORMING THE COMPUTATION OF GOMORY HU CUT-TREES | ||||||||||||
Autor: |
JOAO PAULO DE FREITAS ARAUJO |
||||||||||||
Colaborador(es): |
JOSE EUGENIO LEAL - Orientador FERNANDA MARIA PEREIRA RAUPP - Coorientador |
||||||||||||
Catalogação: | 19/DEZ/2017 | Língua(s): | PORTUGUESE - BRAZIL |
||||||||||
Tipo: | TEXT | Subtipo: | THESIS | ||||||||||
Notas: |
[pt] Todos os dados constantes dos documentos são de inteira responsabilidade de seus autores. Os dados utilizados nas descrições dos documentos estão em conformidade com os sistemas da administração da PUC-Rio. [en] All data contained in the documents are the sole responsibility of the authors. The data used in the descriptions of the documents are in conformity with the systems of the administration of PUC-Rio. |
||||||||||||
Referência(s): |
[pt] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=32393&idi=1 [en] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=32393&idi=2 |
||||||||||||
DOI: | https://doi.org/10.17771/PUCRio.acad.32393 | ||||||||||||
Resumo: | |||||||||||||
Computing the maximum flow value between a source and a terminal nodes in a given network is a classic problem in the context of network flows. Its extension, namely the multi-terminal maximum flow problem, consists of finding the maximum flow values between the all pairs of nodes in a given undirected network. These problems have several applications, especially in the fields of transports, logistics, telecommunications and energy. In this work, we study the recent theory of sensitivity analysis, which examines the influence of edges capacity variation on the multi-terminals maximum flows, and we extend the dynamic computation of multi-terminals flows to the case of more than one edge with variable capacity. Based on this theory, we also relate cut nodes and multiterminals flows, allowing us to develop a competitive method to solve the multiterminal maximum flow problem, when the network has cut nodes. The results of the computational experiments conducted with the proposed method are presented and compared with the results of a classical algorithm, using generated and wellknown instances of the literature. Finally, we apply the presented theory on a problem of identifying protein complexes in protein-protein interaction networks. Through the generalization of an algorithm and a theoretical result about exclusion of minimum cuts, it was possible to reduce the number of maximum flow computations necessary to identify such complexes.
|
|||||||||||||
|