摘要:

AbstractIn the network design problem we are given a weighted undirected graph. We wish to find a subgraph which connects all the original vertices and minimizes the sum of the shortest path weights between all vertex pairs, subject to a budget constraint on the sum of its edge weights. In this note we establish NP‐completeness for the network design problem, even for the simple case where all edge weights are equal and the budget restricts the choice to spanning trees. This result justifies the development of enumerative optimization methods and of approximation algorithms, such as those described in a recent paper by R. Dionne and M. Floria

ISSN:0028-3045    

DOI:10.1002/net.3230080402

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

年代:1978

数据来源: WILEY

摘要:

AbstractWe study a class of five‐stage connecting networks which are generalizations of the AMDF networks recently proposed. The terminals of a network in this class are partitioned into various zones while two terminals of the same zone have a larger number of distinct paths connecting them than two terminals of different zones. Furthermore, to facilitate the analysis of blocking probabilities, we require that the linear graphs (union of all connecting paths) for all intrazone pairs of terminals be isomorphic and fixed, and the linear graphs for all interzone pairs be isomorphic.We show that balanced incomplete block designs can be used to construct large classes of such networks. For a fixed number of distinct paths, we also determine the symmetric linear graph which has the smallest blocking probability, and show that the network which yields this linear graph (for interzone pairs) can always be constructed if a certain balanced incomplete block design exist

ISSN:0028-3045    

DOI:10.1002/net.3230080403

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

年代:1978

数据来源: WILEY

摘要:

AbstractThis paper considers the problem of finding the shortest path between an origin and destination pair in networks whose arc lengths are Euclidean distances. Dijkstra's algorithm and a modified version of Dijkstra's algorithm which is more adaptive to network topology are compared. We demonstrate on the infinite lattice network with diagonal arcs (a prototype of more general sparse Euclidean networks) that on the average the adaptive algorithm expands less than 8.3% the area that would be expanded by the Dijkstra algorithm and in the worst case it expands less than 10.7%. In addition, we present computational results for more general networks.

ISSN:0028-3045    

DOI:10.1002/net.3230080404

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

年代:1978

数据来源: WILEY

摘要:

AbstractIn recent years there have been several extremely successful specialization of the primal simplex method for solving network flow problems. Much of this success is due to the development of highly efficient computational techniques for implementing the primal simplex algorithm. We view these efficient techniques as a new body of knowledge which we call implementation technology. This exposition presents the state‐of‐the‐art of implementation techn

ISSN:0028-3045    

DOI:10.1002/net.3230080405

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

年代:1978

数据来源: WILEY

摘要:

AbstractA new algorithm for updating shortest paths from all vertices to a set of vertices following a decreasing‐length‐modification of some arcs, is presented. The algorithm is based on a formula which has an algebraic analogy with the well‐known Householder formula for inverting modified matrices. The number of operations (i.e., additions and comparisons) required for solving the modified shortest path problem is estimated as 0(mn2), where n is the overall number of vertices and m is a parameter related to the arcs which have been updated. The algorithm proposed here is particularly powerful for solving large‐scale networks with sparse st

ISSN:0028-3045    

DOI:10.1002/net.3230080406

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

年代:1978

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230080407

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

年代:1978

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230080401

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

年代:1978

数据来源: WILEY