COMPUTING MAX FLOWS THROUGH CUT NODES
AUTOR(ES)
Araujo, João Paulo de Freitas, Raupp, Fernanda Maria Pereira, Leal, José Eugenio, Diallo, Madiagne
FONTE
Pesqui. Oper.
DATA DE PUBLICAÇÃO
2017-09
RESUMO
ABSTRACT In this work, the presence of cut nodes in a network is exploited to propose a competitive method for the multi-terminal maximum flow problem. The main idea of the method is based on the relation between cut-trees and cut nodes, which is observed in the context of sensitivity analysis on the variation of edges capacities. Computational experiments were conducted with the proposed algorithm, whose results were compared with the ones of Gusfield, for randomly generated and well-known instances of the literature. The numerical results demonstrate the potential of the method for some classes of instances. Moreover, the proposed method was adapted for the single maximum flow problem, but failed to improve existing running times for the very same classes of instances.
Documentos Relacionados
- Modeling and computing of equivalent bandwidth of multifractal flows
- Pathways of blood flow to and through superficial lymph nodes in the dog.
- Flows of liquid and electrical current through monolayers of cultured bovine arterial endothelium.
- Flows of Bingham Materials Through Ideal Porous Media: an Experimental and Theoretical Study
- Grid Computing and Cloud Computing: analysis of the social,environmental and economic impacts of the collaboration through the resources sharing.