摘要:

AbstractThe residual network reliability concerns networks with perfect edges and nodes that fail independently. It measures the probability that the network's operating nodes remain connected. The Assignment Problem deals with allocating given operating probabilities to the nodes of the network in such a way that the resulting residual network reliability is maximized. in this paper, we show that the Assignment Problem is computationally hard even for the restricted class of split networks, a generalization of threshold networks for which the problem is solvable in polynomial time.

ISSN:0028-3045    

DOI:10.1002/net.3230260402

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

年代:1995

数据来源: WILEY

摘要:

AbstractA new genetic algorithm (GA) for the Steiner Problem in a Graph (SPG) is presented. The algorithm is based on a bitstring encoding of selected Steiner vertices and the corresponding Steiner tree is computed using a deterministic SPG heuristic. The GA is tested on all SPG instances from the OR‐Library having from 500 to 2500 vertices and up to 62,500 edges. For these graphs, The algorithm finds a global optimum in 70% of all program executions and is within 1% from the global optimum value in 90% of all executions. The performance is compared to that of two branch‐and‐cut algorithms and two of the very best deterministic heuristics: an iterated version of the Takahashi and Matsuyama heuristic (ITM) and an iterated version of the Kou, Markowsky, and Berman heuristic (IKMB). in almost all cases, even the worst result ever found by the GA is equal to or better than the best result of ITM and IKMB. Furthermore, while none of the deterministic heuristics or the branch‐and‐cut algorithms are capable of solving all problem instances within a reasonable time limit, The GA finds a near‐optimal solution to every problem in a moderate amo

ISSN:0028-3045    

DOI:10.1002/net.3230260403

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

年代:1995

数据来源: WILEY

摘要:

AbstractThe rectilinear Steiner tree problem asks for a shortest network connectingnterminals in the rectilinear plane (withL1‐metric). The problem can be considered as a special case of the Steiner tree problem in a grid network obtained by drawing horizontal and vertical lines through terminals. The reductions developed for the network variant of the Steiner tree problem can therefore also be used in the rectilinear case. However, computational experience indicates that they are not very powerful in the rectilinear grids. We introduce a limited number of rectilinear reductions based on the geometrical properties of terminals. Experimental results show that these reductions are extremely powerful while being quite simple to verify and easy to implement. For randomly generated problem instances with one terminal per row and column, The number of nonterminals remaining seems to be around 20‐‐25% of their original number. Furthermore, The performance of geometrical reductions improves as the density of terminals in fixed‐size grid

ISSN:0028-3045    

DOI:10.1002/net.3230260404

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

年代:1995

数据来源: WILEY

摘要:

AbstractRestricted Simplicial Decomposition with Side Constraints is a price decomposition method designed for large‐scale nonlinear problems with a set of linear constraints with special structure and an additional set of linear side constraints. The resultant algorithm iterates by solving a linear subproblem subject to the set of structured constraints and asmallnonlinear master problem whose feasible region is defined by the intersection of a simplex and the set of side constraints. The number of variables of the master problem is controlled by a parameter namedr.The conditions required for the parameterrand the rules for dropping extreme points of the simplex are established for global convergence of the algorithm. Computational results are presented for nonlinear network problems with side constraint

ISSN:0028-3045    

DOI:10.1002/net.3230260405

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

年代:1995

数据来源: WILEY

摘要:

AbstractA probabilistic model is proposed that allows one to solve stochastic network reliability problems for tree‐type networks ofNnodes, takingO(logN) time. The considered networks are based on interconnection patterns consisting of complete binary trees in which spare edges are added according to different criteria. We show that the use of this probabilistic model allows one to evaluate, takingO(logN) time, Theaverage connectedness(i.e., The expected number of processing elements still functioning in the presence of random faults) of dynamically reconfigurable fault‐tolerant VLSI systems which are based on such tree‐based structures. Finally, numerical results obtained from the model are provided that show that, given a fixed chip silicon area, several of the analyzed VLSI architectures have a notably greater expected number of working processing elements w.r.t. complete binary trees, in the presence of a given fault distrib

ISSN:0028-3045    

DOI:10.1002/net.3230260406

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

年代:1995

数据来源: WILEY

摘要:

AbstractThis paper considers the Generalized Minimum Spanning Tree Problem (GMSTP). Given an undirected graph whose nodes are partitioned into mutually exclusive and exhaustive node sets, The GMSTP is then to find a minimum‐cost tree which includes exactly one node from each node set. Here, we show that the GMSTP isNP‐hard and that unlessP = NPno polynomial‐time heuristic algorithm with a finite worst‐case performance ratio can exist for the GMSTP. We present various integer programming formulations for the problem and compare their linear programming relaxations. Based on the tightest formulation among the ones proposed, a dual‐based solution procedure is developed and shown to be efficient from computing ex

ISSN:0028-3045    

DOI:10.1002/net.3230260407

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

年代:1995

数据来源: WILEY

摘要:

AbstractThe Pickup Delivery Location Problem (PDLP) is a generalization of the Traveling Salesman Location Problem (TSLP) in which the daily tour involves pickup and delivery provided to customers by a vehicle of a given capacity. Two heuristics are suggested: The first is an extension of a method introduced by Simchi‐Levi and Berman for solving the TSLP. Its worst‐case relative error is shown to be bounded by 1. The second is based on a simple ranking of customers according to their probabilities for positive demand and their weighted average distances from all other locations. in addition, The fully polynomial algorithm of Berman and Simchi‐Levi is extended for solving PDLPs on tree networks. Both heuristics were tested on small‐size general networks and medium‐size tree networks. The average relative error over all test problems in the first class did not exceed 2.5% for the first heuristic and 1% for the second. in most cases, both produced the optimal solution. in about 56% of the tree network problems (with up to 80 nodes), Theoptimal home location of the server was found by at least one of the heuristics, and in about 94% of the problems, Theoptimal or an adjacent node was found by at least one of the h

ISSN:0028-3045    

DOI:10.1002/net.3230260408

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

年代:1995

数据来源: WILEY

摘要:

AbstractBroadcasting refers to the process of dissemination of a set of messages originating from one node to all other nodes in a communication network. We assume that, at any given time, a node can transmit a message along at most one incident link and simultaneously receive a message along at most one incident link. We first present an algorithm for determining the amount of time needed to broadcastkmessages in an arbitrary tree. Second, we show that, for everyn, There exists a graph withnnodes whosek‐message broadcast time matches the trivial lower bound ⌈ logn⌉ +k− 1 by designing a broadcast scheme for complete graphs. We call those graphs minimal broadcast graphs. Finally, we construct annnode minimal broadcast graph with fewer than (⌈logn⌉ + 1)2⌈

ISSN:0028-3045    

DOI:10.1002/net.3230260409

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

年代:1995

数据来源: WILEY

摘要:

AbstractWe study two relatedconstrained shortest path problemsin which the nodes are partitioned into series/parallel clusters. These and many other constrained shortest path problems occur in optimizing the layout of private networks embedded in a larger telecommunications network. The first problem deals with a situation in which, in addition to each edge being assigned a nonnegative integer weight, each node is also assigned a nonnegative integer weight, and the constraint on the path is that the total node weight incurred within each cluster should not exceed a given nonnegative integer /. The second problem considers two constraints: (i) a path cannot contain more than / nodes in one cluster and (ii) a path must traverse through at least one of a given set of special nodes in each of the traversed clusters. We propose efficient exact algorithms for solving both problems. Numerical examples are also provided.

ISSN:0028-3045    

DOI:10.1002/net.3230260410

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

年代:1995

数据来源: WILEY

摘要:

AbstractEven though the problem of computing Steiner minimal trees (SMTs) in the plane is well known to beNP‐hard, There exist heuristic algorithms which run in polynomial time. Recent research results have shown that the problem in three dimensions is demonstrably more difficult. This paper approaches the development of a heuristic for the problem utilizing the Delaunay triangulation in 3‐space to compute suboptimal SMTs. Computational results are also provi

ISSN:0028-3045    

DOI:10.1002/net.3230260411

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

年代:1995

数据来源: WILEY