摘要:

AbstractThree transformations on networks that reduce the all‐terminal network reliability (probability of connectedness) of a network are shown not to increase any coefficient in one form of the reliability polynomial of the network. These transformations yield efficiently computable lower bounds on each coefficient of the reliability polynomial. A further transformation due to Lomonosov is shown not to decrease any coefficient in the reliability polynomial, leading to an efficiently computable upper bound on each coefficient. The resulting bounds on coefficients can, in turn, be used to obtain a substantial improvement on the Ball—Provan strategy for computing lower and upper bounds on the all‐terminal reliability. ©1993 John Wiley&Son

ISSN:0028-3045    

DOI:10.1002/net.3230230103

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

年代:1993

数据来源: WILEY

摘要:

AbstractWe present some existing and some new formulations for the Steiner tree and Steiner arborescence problems. We show the equivalence of many of these formulations. In particular, we establish the equivalence between the classical bidirected dicut relaxation and two vertex weighted undirected relaxations. The motivation behind this study is a characterization of the feasible region of the dicut relaxation in the natural space corresponding to the Steiner tree problem. ©1993 by John Wiley&Sons, Inc

ISSN:0028-3045    

DOI:10.1002/net.3230230104

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

年代:1993

数据来源: WILEY

摘要:

AbstractIn this paper, we further study the properties of bipartite permutation graphs. We give first efficient parallel algorithms for several problems on bipartite permutation graphs. These problems include transforming a bipartite graph into a strongly ordered one if it is also a permutation graph; testing isomorphism; finding a Hamiltonian path/cycle; solving a variant of the crossing number problem; and others. All these problems can be solved inO(log2n) time withO(n3) processors on a Common CRCW PRAM. We also show that the minimum fill‐in problem for bipartite permutation graphs can be solved efficiently by a randomized parallel algorithm. ©1993 by John Wiley&Sons, I

ISSN:0028-3045    

DOI:10.1002/net.3230230105

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

年代:1993

数据来源: WILEY

摘要:

AbstractWe present a polynomial algorithm for the minimum cost network flow problem (MCNF). It is a dual algorithm that is based on canceling positive augmenting cuts, which are the duals of negative augmenting cycles. We focus on cancelingmost helpful total cuts, which are cuts together with augmentation amounts that lead to the maximum possible increase in the dual objective function. We show how to compute a most helpful total cut and give a rigorous dual conformal decomposition theorem. Canceling most helpful cuts is, in spirit, dual to an algorithm of Weintraub as modified by Barahona and Tardos. We also show how our algorithm specializes to the case of shortests–tpath with nonnegative distances, show that this specialization is not finite for real data, and show that our bound on the number of cancellations is essentially tight. ©1993 by John Wiley&Sons, I

ISSN:0028-3045    

DOI:10.1002/net.3230230106

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

年代:1993

数据来源: WILEY

摘要:

AbstractA two‐stage rearrangeable broadcast network (called an ordinary network here) that has been studied recently has a partial concentrator on the input side. We extend this study to a network with two partial concentrators: one on the input side and the other on the output side. We first study the network as a connection network and derive conditions for its rearrangeability. We show that the conditions are tight in some cases. We then show that a particular construction that meets the rearrangeability conditions actually yields a broadcast network. ©1993 John Wiley&Sons, I

ISSN:0028-3045    

DOI:10.1002/net.3230230107

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

年代:1993

数据来源: WILEY

摘要:

AbstractA new class of chordal graphs, containing the class of strongly chordal graphs, is introduced. It is shown that these graphs, called doubly chordal graphs, are related to acyclic hypergraphs and are recognizable in polynomial time. Furthermore, after proving that the Steiner tree and the connected domination problems are polynomially solvable for doubly chordal graphs, it is shown that both problems are NP‐hard for a class of chordal graphs (called Helly chordal graphs) containing the class of doubly chordal graphs. ©1993 John Wiley&Sons, I

ISSN:0028-3045    

DOI:10.1002/net.3230230108

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

年代:1993

数据来源: WILEY

摘要:

AbstractThis paper is concerned with information dissemination in a tree. It is assumed that a vertex can either transmit or receive a message and an informed vertex can transmit it to only one of its neighbors at a time. Under a minisum criterion, a necessary and sufficient condition for an optimal call sequence at each vertex is established. Based on this, anO(NlogN) algorithm is designed to find optimal call sequences at all vertices and to determine the broadcast center of a tree—the set of all vertices from which minisum broadcasting can be accomplished. ©1993 John Wiley&Sons, I

ISSN:0028-3045    

DOI:10.1002/net.3230230109

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

年代:1993

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230230102

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

年代:1993

数据来源: WILEY