摘要:

AbstractIn this paper we consider the Steiner problem in graphs which is the problem of connecting together, at minimum cost, a number of vertices in an undirected graphs. We present a formulation of the problem as a shortest spanning tree (SST) problem with additional constraints. By relaxing thses additional constraints in a lagrangean fashion we obtain a lower bound for the problem based upon the solution of an unconstrained SST problem. Problem reduction tests derived from both the original problem and the lagrangean relaxation are given. Incorporating the bound and the reduction tests into a tree search procedure enables us to solve problems involving the connection of up to 1250 vertices in a graph with 62500 edges and 2500 vertices.

ISSN:0028-3045    

DOI:10.1002/net.3230190102

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

年代:1989

数据来源: WILEY

摘要:

AbstractA 2‐threshold graph is defined to be the edge‐union of two threshold graphs. We prove that all chordless cycles of size at least 5 and their complements are forbidden for 2‐threshold graphs. We also obtain a sufficient condition for a 2‐threshold graph to be a comparability graph. Finally, we show that 2‐threshold graphs can have at most three cutpoints and obtain efficient algorithms to recognize, decompose and obtain a maximum stable set of 2‐threshold graphs with exactly thre

ISSN:0028-3045    

DOI:10.1002/net.3230190103

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

年代:1989

数据来源: WILEY

摘要:

AbstractRelationships among graph invariants such as the number of vertices, diameter, connectivity, maximum and minimum degrees, and regularity are being studied recently, motivated by their usefulness in the design of fault‐tolerant and low‐cost communication and interconnection networks. A graph is called a (d,c,r) graph if it has diameterd, connectivityc, and regularityr. The minimum number of vertices in (d, 1,3), (d,2,3), (d,3,3), and (d,c,c) graphs have been reported in the literature. In this paper, the minimum number of vertices in a (d,c,r) graph withr>cis determined, thereby exhausting all the possible choices of values ford,c, andr. Our proof is constructive and hence we get a collection of optimal (d,c,r) gra

ISSN:0028-3045    

DOI:10.1002/net.3230190104

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

年代:1989

数据来源: WILEY

摘要:

AbstractWe present the notion of a generalized inverse of a digraph. The notion includes two different kinds of event networks, both discussed in literature. We show how different techniques used separately in both special cases can be applied to the general case. We prove that the problem of minimization of the number of dummy arcs among al event networks having the minimum number of vertices is polynomially transformable to a certain covering problem. We use the transformation method to provide a necessary and sufficient condition for a certain suboptimal solution to the problem to be optimal in general. We show that the verification of this condition can be done in polynomial time.

ISSN:0028-3045    

DOI:10.1002/net.3230190105

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

年代:1989

数据来源: WILEY

摘要:

AbstractIf a practical network is modelled as a graph in which the lines are perfect but the points may fail then a primary measure of vulnerability is the point connectivity of the graph and one possible secondary measure of vulnerability is the number of minimum point disconnecting sets. The graph shold have the maximum possible point connectivity and the minimum number of point disconnecting sets. A lower bound for the number of minimum point disconnecting sets is derived by identifying points with identical adjacencies.

ISSN:0028-3045    

DOI:10.1002/net.3230190106

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

年代:1989

数据来源: WILEY

摘要:

AbstractIn this paper we study the problem of finding a minimum‐weight collection of edges in a planar graph which separates a given set of vertices from the outer face. This problem has two variants: either a given embedding is specified, or the best possible embedding is to be found. We present polynomial‐time algorithms for each case. We show how to use these results to recognize a special case of the steiner tree problem in graphs which is polynomially solvable. A closely related problem is shown to beNP‐com

ISSN:0028-3045    

DOI:10.1002/net.3230190107

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

年代:1989

数据来源: WILEY

摘要:

AbstractConvex transportation problems represent an important special class of convex network flow problems, with particular applications in telecommunications, economics and engineering. This paper describes an implementation of an “exact” Newton algorithm for separable convex transportation problems. Previously in the literature, only approximate Newton algorithms had been described for the general case of convex network flow problems. The special structure of the transportation problem is used to simplify computation of dual multiplier estimates. In general, this would require factorization of a square matrix of dimensionn+m− 1, werenis the number of sources andmis the number of sinks. By exploiting structure, the work of factorization is limited to a square matrix of dimensionn− 1 orm− 1, whichever is smaller. Some computational experience is described. We also note an analogy between this Newton algorithm for convex problem and a particular variant of Karmarkar's algorithm for linear

ISSN:0028-3045    

DOI:10.1002/net.3230190108

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

年代:1989

数据来源: WILEY

摘要:

AbstractSome variations on Eulerian partitions of edge sets and arc sets are discussed. We consider partitions into (odd) paths, chains and antipaths; these are paths where every second are is reversed. Packing problems are also examined and min‐max results are derived by using network flow technique

ISSN:0028-3045    

DOI:10.1002/net.3230190109

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

年代:1989

数据来源: WILEY

摘要:

AbstractWe show how to locate optimallypnew facilities (servers) on a network so as to minimize cost, where cost can be any convex function of the distances between demand points (nodes) and a closest server. The algorithm is generally practical only for smallp(perhaps 2, 3, or 4), but it admits a large number of servers with locations fixed beforehand. The classicalp‐median,p‐center, andp‐facility cent‐dian problems are special cases. Other problems of this form include a large number of obnoxious facility problems, problems in which the objective is to minimize anLknorm of distances, and a wide variety of problems, problems in which the objective is to minimize anLknorm of distances, and a wide variety of problems in which equity or social welfare is a a

ISSN:0028-3045    

DOI:10.1002/net.3230190110

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

年代:1989

数据来源: WILEY

摘要:

AbstractRelations are established between the domination and minimum domination invariants and a matroid invariant known as the Crapo β‐invariant. Using these results, it is possible to extend well‐known results of domination theory. Moreover, the proofs of these results are considerably simplified. Matroid theory is made available to reliability applications by introducing a certain regularity assump

ISSN:0028-3045    

DOI:10.1002/net.3230190111

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

年代:1989

数据来源: WILEY