摘要:

AbstractThe problem of routing flow in a network of computers is extremely complex. This is especially formidable when routing is to be incorporated in iterative analysis and design. Among the properties of desirable flow patterns is low average delay from message inception to arrival. In this paper, we discuss procedures for minimizing average delay subject to a set of flow constraints. Heuristic routing procedures are presented and compared to optimum routing procedures. Computational experience is given.

ISSN:0028-3045    

DOI:10.1002/net.3230010202

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1971

数据来源: WILEY

摘要:

AbstractA graph theoretic version of Steiner's problem in plane geometry is described. An approach for solving this problem, related to Melzak's solution to Steiner's problem, is presented. The problems of finding “shortest route” and “minimal spanning tree” in graphs become special cases of the Steiner's problem in graphs. It is shown that a solution to this problem also provides us with a solution to the problems of finding a minimum externally stable set and a maximum internally stable set in

ISSN:0028-3045    

DOI:10.1002/net.3230010203

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1971

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230010204

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1971

数据来源: WILEY

摘要:

AbstractThis paper develops techniques which can be applied to long range planning studies for the domestic long haul communications network. The problem studied is how to select a path through the network for each point‐to‐point demand for communications channels, so that the total network cost is minimized. The problem is to minimize total network cost, subject to multicommodity flow requirements and concave link cost functions. Finding an exact solution is difficult because of the concavity of the cost functions and the complexity (100 to 200 nodes and 200 to 300 links) of the network structure. A specialized technique is developed to provide locally optimal solutions to the problem, one of minimizing a concave function over a convex constraint set. When the link cost displays a fixed charge, a modification of the iterative algorithm provides acceptable a modification of the iterative algorithm provides acceptable solutions. Even though the global optimum cannot be found amidst the immense number of local optima, several sample problems demonstrate the value of the techniques developed.A companion paper will extend this work to the dynamic routing problem, of deciding how to route future demands and install transmission facilities so as to minimize the present worth of expenditures during the study interval. The methods and goals of these modeling efforts will be discussed in the companion pa

ISSN:0028-3045    

DOI:10.1002/net.3230010205

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1971

数据来源: WILEY

摘要:

AbstractThis paper presents an efficient algorithm for solving transportation problems. The improvement over the existing algorithms of the “primal‐dual” type [3], [5]consists in modifying the “potential‐raising” stages of the solution process in such a way that negative‐cost arcs are removed so that the Dijkstra's algorithm may be applied. Especially, the algorithm requires at most n3additions and comparisons when applied to an n‐by‐n assignment problem, as compared with the theoretical upper bound proportional to n4for the number of such operations required by currently available methods. Furthermore, auxiliary techniques of simplifying the original network by means of “reduction” and “induction” are also introduced as useful tools to treat large‐scale problems and special

ISSN:0028-3045    

DOI:10.1002/net.3230010206

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1971

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230010201

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1971

数据来源: WILEY