摘要:

AbstractThe complexity of many combinatorial algorithms is directly related to the number of upsets (filters) in an underlying partial order or, equivalently, to the number of downsets (ideals) that are the complements of upsets. In this paper, we investigate the expected number of upsets in randomly generated two‐dimensional partial orders and present a number of new results, together with simple combinatorial proofs of some known results. As an application of our results, we show that some well‐known algorithms for precedence constrained scheduling have nonpolynomial expected time and storage complex

ISSN:0028-3045    

DOI:10.1002/net.3230210502

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

年代:1991

数据来源: WILEY

摘要:

AbstractThe Gomory–Hu cut tree is a compact and efficiently computed representation of selected minimumedgecuts in a weightedundirectedgraphG=(V, E)withnnodes. It represents ( n2) minimum cuts, one for each pair of nodes inG, and can be constructed with onlyn− 1 flow computations. In this article, we generalize the types of cut‐trees that can be efficiently constructed. We solve the open problem, posed by Hu [9], of constructing withn− 1 flows acut‐treefor minimumnode weightedcuts in an undirected graph. We then show how to build cut‐trees that compactly represent the minimum edge cuts indirectedgraphs, partially solving the open problem of constructing cut‐trees for weighted edge cuts in

ISSN:0028-3045    

DOI:10.1002/net.3230210503

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

年代:1991

数据来源: WILEY

摘要:

AbstractWhen computing the reliability of a system consisting of several components, it is usually assumed that the components are statistically independent of each other. In case the components are associated, it is known that this leads to underestimation if the system is a series, whereas the converse holds for parallel systems. In this paper, we consider general monotone systems and study the error resulting from the independence assumption when the component states are, in fact, distributed according to certain dependence models. We also consider some applications of the results to network systems.

ISSN:0028-3045    

DOI:10.1002/net.3230210504

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

年代:1991

数据来源: WILEY

摘要:

AbstractThis paper considers a sharing problem of distributing a given quantity of resources to a set of demand nodes in a network as equally as possible. We study the case in which the resources are of two distinct kinds and propose a polynomial time algorithm for it by reducing the problem to the one‐commodity sharing proble

ISSN:0028-3045    

DOI:10.1002/net.3230210505

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

年代:1991

数据来源: WILEY

摘要:

AbstractIn this article, we consider an oligopolistic market equilibrium problem defined on a bipartite network with suppliers on one side and demand regions on the other. With certain reasonable conditions on the supply and demand functions, we shall first show that the equilibrium solution exists and is unique and then show that this equilibrium solution is also Lipschitz continuous and directionally differentiable with respect to smooth perturbations.

ISSN:0028-3045    

DOI:10.1002/net.3230210506

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

年代:1991

数据来源: WILEY

摘要:

AbstractThis article considers the reliability problem of computing the probability that the root‐vertex of a directed network can communicate with all other vertices of the network when arcs are subject to random failure. Ball and Provan have observed that when the network contains no directed cycles this probability can be computed in linear time. This paper considers the problem when the network is almost acyclic, that is, when the number of simple directed cycles in the network is small. A new algorithm for computing network reliability is presented. The algorithm is based on expressing the reliability in terms of the derivative of the network reliability with respect to the reliability of an arc. Given a class of networks with a fixed number of simple cyclesc, the computation requirements of the new algorithm areO(|E|c+1), where |E| is the number of arcs. Comparison of coded versions of this algorithm and one of Ball's as well as theoretical comparison with one of Buzacott's confirm that this algorithm is to be preferred when the number of directed cycles is small in comparison to the number of vertice

ISSN:0028-3045    

DOI:10.1002/net.3230210507

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

年代:1991

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230210501

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

年代:1991

数据来源: WILEY