摘要:

AbstractMany bounds for the all‐terminal reliability of computer networks have been proposed. Of those computable in polynomial time, the Ball‐Provan bounds and the Lomonosov Polesskii bounds provide the tightest estimates. A strategy is developed here using linear programming to obtain bounds which are tighter than both the Lomonosov‐Polesskii and the Ball‐Provan bounds. Computational results on these new bounds are also r

ISSN:0028-3045    

DOI:10.1002/net.3230180102

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

年代:1988

数据来源: WILEY

摘要:

AbstractIn this paper we study the probabilistic behavior of the farthest neighbor heuristic for finding the longest Hamiltonian tour in a graph. We assume the edge weights are independent random variables uniformly distributed in [0,1]. If F, is the length of the heuristic tour and L, the optimal tour then Fn/Ln→ 1 a.s. as n → α. We also show that Ln/n → 1 a.s. as

ISSN:0028-3045    

DOI:10.1002/net.3230180103

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

年代:1988

数据来源: WILEY

摘要:

AbstractThis paper solves the minimum augmentation problem for a given tree and positive integer k, that is, to make a tree k‐edge‐connected by adding the minimum number of edges. It is shown that the minimum number of edges is the least integer not less than a half of the deficiency of the tree which is defined as the sum of k‐(degree) over all the vertices whose degrees are less than k. The proof is constructive and gives a polynomial‐time algorithm for constructing such an augme

ISSN:0028-3045    

DOI:10.1002/net.3230180104

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

年代:1988

数据来源: WILEY

摘要:

AbstractWe show that the digraphs proposed independently by Imase and Itoh, and Reddy, Pradhan and Kuhl to minimize diameters essentially retain all the nice properties of de Bruijn digraphs and yet are applicable to any number of nodes. In particular we give results on the number of loops, the link connectivities and connectivities, the embedding properties and the self‐routing properties for these digraph

ISSN:0028-3045    

DOI:10.1002/net.3230180105

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

年代:1988

数据来源: WILEY

摘要:

AbstractIn many services (e.g., delivery, or customer pickup vehicles) the service unit usually visits a number of demand points on a single multistop tour. Typically, at a specific time of the day, the unit receives the list of waiting calls and immediately starts a tour of the network that includes all waiting customers. The multistop location problem is to find the home location for the service unit. We focus on the minimax criterion for the multistop problem defined on a tree network. Each potential list of customers is associated with the length of its respective tour and with some weight. We seek for the home location of the unit that minimizes the maximum weighted tour length over all feasible customer lists. We consider several weight functions and obtain results that reveal additional properties of the classical absolute center of the tree.

ISSN:0028-3045    

DOI:10.1002/net.3230180106

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

年代:1988

数据来源: WILEY

摘要:

AbstractA directed graph G with a source s and a sink t is called a p‐graph if every edge of G belongs to an elementary (s,t)‐path of G. If C is a cycle of the p‐graph G then a cyclic cover of C is a set of (s,t)‐paths of G that contains all the edges of C. A cyclic cover Q is minimal if for every path P e Q, Q = {P} is not a cover of C. The following property is known and was used in providing an important result in network reliability: A cyclic p‐graph has a cycle C and a path P such that P is not contained in any minimal cover of C. In this note we give a simpler proof of this property which provides more insight into the nature of cyclic covers in

ISSN:0028-3045    

DOI:10.1002/net.3230180107

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

年代:1988

数据来源: WILEY

摘要:

AbstractWe investigate the role convexity plays in the efficient solution to the Steiner tree problem. In general terms, we show that a Steiner tree problem is always computationally easier to solve when the points to be connected lie on the boundary of a “convex” region. For the Steiner tree problem on graphs and the rectilinear Steiner tree problem, we give definitions of “convexity” for which this condition is sufficient to allow a polynomial algorithm for finding the optimal Steiner tree. For the classical Steiner tree problem, we show that for the standard definition of convexity, this condition is sufficient to allow a fully polynomial approximation

ISSN:0028-3045    

DOI:10.1002/net.3230180108

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

年代:1988

数据来源: WILEY

摘要:

AbstractThe concept of vulnerability of a network, by which we mean the susceptibility of the network to attack, is very useful for the design of networks such as computer networks and communication networks. In this paper, a directed flow network, in which a nonnegative real number called edge capacity or capacity is associated with each edge is considered. If an edge in a network is destroyed, the value of maximum flow between two vertices in the network is decreased in general. If the decrease of the value of maximum flow by the destruction is large, the degree of influence of the edge on the vulnerability of the network is considered to be large. Two indices measuring the degree of influence of an edge on the vulnerability in the above sense are proposed and their properties are studied in this paper. Furthermore, the two indices are generalized to functions measuring the degree of influence of an edge on the vulnerability in a network.

ISSN:0028-3045    

DOI:10.1002/net.3230180109

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

年代:1988

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230180101

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

年代:1988

数据来源: WILEY