Premium
A functional equation for finding the largest expected capacity of a graph
Author(s) -
Sancho N. G. F.
Publication year - 1989
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230190208
Subject(s) - node (physics) , mathematics , graph , functional equation , arc (geometry) , combinatorics , path (computing) , dynamic programming , reliability (semiconductor) , mathematical optimization , discrete mathematics , computer science , differential equation , mathematical analysis , physics , power (physics) , quantum mechanics , geometry , programming language
Given a graph in which every arc ( i, j ) has two numbers ρ ij and C ij associated with it representing the reliability and capacity, respectively, a dynamic programming formulation is derived for finding the path from any node i to terminal node N with the largest expected capacity. It is shown that the functional equation obtained may not necessarily be governed by the principle of optimality.