摘要:

AbstractIn this paper we consider a natural probabilistic variation of the classical minimum spanning tree problem (MST), which we call the probabilistic minimum spanning tree problem (PMST). In particular, we consider the case where not all the points are deterministically present, but are present with certain probability. We discuss the applications of the PMST and find a closed‐form expression for the expected length of a given spanning tree. Based on these expressions, we prove that the problem isNP‐complete. We further examine some interesting combinatorial properties of the problem, establish the relation of the PMST with the MST and the network design problem, and examine some cases where the problem is solvable in polynomial time. We finally characterize the asymptotic behavior of reoptimization strategies, in which we find the MST or the Steiner tree, respectively, among the points that are present on a particular instance, and the PMST, in the case in which points are randomly distributed in the Euclidean plane and in the case in which the costs of the ares are randomly distributed. In both cases the PMST is within constant factors from both strateg

ISSN:0028-3045    

DOI:10.1002/net.3230200302

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

年代:1990

数据来源: WILEY

摘要:

AbstractA simplified model of a communications network is a probabilistic graph in which each edge operates with the same probability. Theall‐terminal reliability, or probability that all nodes are connected, can be expressed as a polynomial in the edge operation probability. The coefficients of this polynomial are obtained from an interval partitioning of the cographic matroid, and only the first few coefficients can be computed efficiently. One of the best sets of efficiently computable reliability bounds is the Ball‐Provan bounds. These bounds are obtained using the efficiently computable coefficients and can be improved substantially if additional coefficients are known. In this paper, we develop a Monte Carlo method for estimating additional coefficients by randomly sampling over spanning trees of the network. Confidence intervals for all‐terminal reliability are obtained by using these estimates as additional constraints in the Ball‐Provan bounds. This approach has some advantages over conventional Monte Carlo point estimate methods. In particular, the computational complexity does not depend on the reliability of the

ISSN:0028-3045    

DOI:10.1002/net.3230200303

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

年代:1990

数据来源: WILEY

摘要:

AbstractAk‐treeis defined recursively as follows: The complete graphKkonkpoints is ak‐tree. Given ak‐treeGonn≤kpoints, ak‐tree onn+ 1 points is obtained by adding a new pointuand edges connectinguto every point of aKkinG. A graph is apartial k‐treeif it is a subgraph of somek‐tree. In this paper, we establish some interesting properties of partial 3‐trees and show that a graph is a partial 3‐tree if and only if it has no subgraph contractible toK5,K2.2.2C8(1, 4), orK2≤C5. A graphGis said to becontractibleto a graphHifHcan be obtained fromGby a sequence of edge contractions. hitherto, such a characterization of partialk‐trees was known only

ISSN:0028-3045    

DOI:10.1002/net.3230200304

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

年代:1990

数据来源: WILEY

摘要:

AbstractIn the present paper we deal with equipartition problems for special classes of trees, i. e., spiders, stars, worms, and caterpillars. We prove that the equipartition problem is NP‐complete for spiders (and, hence, for general trees); on the other hand, we give efficient polynomial‐time algorithms for stars, worms, and caterpill

ISSN:0028-3045    

DOI:10.1002/net.3230200305

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

年代:1990

数据来源: WILEY

摘要:

AbstractThe resource‐constrained minimum weighted arborescence problem, a 0‐1 integer programming model with application in hierarchical distribution network design, is introduced. Since the model is NP‐hard, an enumeration method is required to solve it to optimality. Lagrangean decomposition, a special form of Lagrangean relaxation, is applied to the model. Both analytically and empirically, Lagrangean decomposition is shown to improve on bounds obtained by a conventional Lagrangean relaxation. An enumeration algorithm, that embeds a specialized Lagrangean dual ascent scheme to solve a Lagrangean decomposition dual, is designed, and problems with up to 1000 0‐1 variables are

ISSN:0028-3045    

DOI:10.1002/net.3230200306

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

年代:1990

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230200301

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

年代:1990

数据来源: WILEY