摘要:

AbstractWe consider the problem of finding the (Euclidean) shortest pathSP(s, t)between two pointssandtin the plane, in the presence of obstacles. Lee and Preparata considered a special case, where the obstacles arendisjoint segments parallel to they‐axis. LetVbe the set consisting ofs, tand the endpoints of thensegments. They showed that the shortest path betweensand any point inVis monotone with respect to thex‐axis. LetSPT(V)denote the Shortest Path Tree onVthat consists of the shortest path fromsto each point inV. They presented anO(nlogn) algorithm for constructingSPT(V)and an Ω(nlogn) lower bound for findingSP(s, t). Their algorithm first sorts the segments according to their abscissae and then constructsSPT(V)by sweeping a vertical line fromstot. Their lower bound proof is based on the fact that any algorithm that findsSP(s, t)must actually sort the segments according to their abscissae. We prove that even if the segments are given in sorted order of their abscissae, Ω(nlogn) time is still required to findSPT(V). The sweep‐line technique for findingSP(s, t)can be used wheneverSP(s, t)is monotone. Lee and Preparata stated thatSP(s, t)is monotone for arbitrary obstacles, if the projections of any two obstacles on thex‐axis do not overlap. We prove thatSP(s, t)is monotone if the projections of any two obstacles do notpartiallyoverlap, andsandtare, respectively, to the left and to the right of all the

ISSN:0028-3045    

DOI:10.1002/net.3230210302

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

年代:1991

数据来源: WILEY

摘要:

AbstractWe present an enhanced hypercube architecture and develop a corresponding routing scheme to realize arbitrary permutations in this paper. In particular, we design a rearrangeable and reconfigurable static hypercube architecture called theGeneralized Folding‐Cubein the circuit switching environment. In the proposed hypercube, we show that if each connection between two neighboring nodes consists of two pairs of links (two full‐duplex communication lines) the hypercube can handle two independent permutations simultaneously. This hypercube architecture can also be used as an efficient reconfigurable netw

ISSN:0028-3045    

DOI:10.1002/net.3230210303

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

年代:1991

数据来源: WILEY

摘要:

AbstractWe investigate the minimum weight path problem in networks whose link weights and link delays are both functions of time. We demonstrate that, in general, there exist cases in which no finite path is optimal leading us to define an infinite path (naturally, containing loops) in such a way that the minimum weight problem always has a solution. We also characterize the structure of an infinite optimal path. In many practical cases, finite optimal paths do exist. We formulate a criterion that guarantees the existence of a finite optimal path and develop an algorithm to find such a path. Some special cases, e.g., optimal loopless paths, are also discussed.

ISSN:0028-3045    

DOI:10.1002/net.3230210304

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

年代:1991

数据来源: WILEY

摘要:

AbstractThe resilience of a network is the expected number of pairs of nodes that can communicate. Computing the resilience of a network is a #P‐complete problem even for planar networks with fail‐safe nodes. We generalize anO(n2) time algorithm to compute the resilience ofn‐nodek‐tree networks with fail‐safe nodes to obtain anO(n)time algorithm that computes the resilience ofn‐node partialk‐tree networks with edge and node failures (given a fixedkand an embedding of the partialk‐t

ISSN:0028-3045    

DOI:10.1002/net.3230210305

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

年代:1991

数据来源: WILEY

摘要:

AbstractThis paper studies the reliability covering problem, in which given routes provides service to various stops (e.g., of a transit system). If the routes are subject to failure, it is desired to find the probability that all stops will be covered by an operating route. It is shown that this problem is NP‐hard even when routes are defined with respect to an underlying tree. Polynomially solvable cases are developed when some additional structure is imposed on the routes of a tree: e.g., when the routes are directed paths of a rooted directed tree. These cases generalize reliability computations for consecutivek‐out‐of‐nsystems as well as the extensions to consecutively connected systems studied by Shanthikumar and by Hwang

ISSN:0028-3045    

DOI:10.1002/net.3230210306

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

年代:1991

数据来源: WILEY

摘要:

AbstractWe consider probabilistic graphsG=(V, E)in which each edgexy∈Efails independently with probabilityq. The reliability measure studied is pair‐connectivity, the expected number of pairs of connected vertices. We examine how the coefficients of the pair‐connected reliability polynomial are determined by the subgraph structure ofG, and we use these results to show that in most cases there does not exist a uniformly optimaln‐vertex,m‐e

ISSN:0028-3045    

DOI:10.1002/net.3230210307

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

年代:1991

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230210308

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

年代:1991

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230210309

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

年代:1991

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230210301

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

年代:1991

数据来源: WILEY