摘要:

AbstractLehman observed that star—delta and delta—star transformation cannot always be applied to networks with perfect (unfailing) vertices so as to exactly preserve reliability, and Rosenthal and Frisque introduced imperfect vertices to make exact delta—star transformations possible. We give an explicit condition that is satisfied if and only if a network with perfect vertices can be subjected to an exact star—delta or delta—star transformation, and we discuss the introduction of imperfect faces to make exact star—delta transformations possible. ©1993 by John Wil

ISSN:0028-3045    

DOI:10.1002/net.3230230302

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

年代:1993

数据来源: WILEY

摘要:

AbstractLetG=(A, B; E)be a bipartite graph. Lete1,e2be nonnegative integers, andf1,f2nonnegative integer‐valued functions onV(G)such thatei≦ |E| ≦e1+e2andfi(v)≦d(v)≦f1(v)+f2(v)for allvϵV(G)(i= 1, 2). Necessary and sufficient conditions are obtained forGto admit a decomposition in spanning subgraphsG1= (A, B; E1) andG2= (A, B; E2) such that |Ei| ≦eianddGi(v)≦fi(v)for allvϵV(G)(i= 1, 2). The result generalizes a known characterization of bipartite graphs with ak‐factor. Its proof uses flow theory and is a refinement of the proof of an analogous result due to Folkman and Fulkerson. By applying corresponding flow algorithms, the described decomposition can be found in polynomial time if it exists. As an application, an assignment problem is solved. ©1993 by Jo

ISSN:0028-3045    

DOI:10.1002/net.3230230303

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

年代:1993

数据来源: WILEY

摘要:

AbstractThis paper presents heuristics that are based on a tour splitting of a general routing tour for solving the general capacitated routing problem (GCRP). This problem is a generalization of the vehicle routing problem (VRP) and the capacitated arc routing problem (CARP). For the VRP, heuristics that consist of an optimum partitioning of a TSP tour generated by Christofides are known and have a worst‐case error of 7/2 − 3/qfor evenq, whereqis the capacity of the vehicles. If we apply a partitioning to an optimum TSP tour, the worst‐case error becomes 3 − 2/qfor evenq. We generalize these results to the GCRP and give also some lower bounds. ©1993 John Wiley&S

ISSN:0028-3045    

DOI:10.1002/net.3230230304

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

年代:1993

数据来源: WILEY

摘要:

AbstractIn this work, we compute the distribution ofL*, the length of a shortest(s, t)path, in a directed networkGwith a source nodesand a sink nodetand whose arc lengths are independent, nonnegative, integer valued random variables having finite support. We construct a discrete time Markov chain with a single absorbing state and associate costs with each transition such that the total cost incurred by this chain until absorption has the same distribution as doesL*. We show that the transition probability matrix of this chain has an upper triangular structure and exploit this property to develop numerically stable algorithms for computing the distribution ofL* and its moments. All the algorithms are recursive in nature and are illustrated by several examples. ©1993 by John Wiley&Sons, Inc

ISSN:0028-3045    

DOI:10.1002/net.3230230305

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

年代:1993

数据来源: WILEY

摘要:

AbstractLetGbe a probabilistic(n,m)graph in which each vertex exists independently with fixed probabilityp, 0

ISSN:0028-3045    

DOI:10.1002/net.3230230306

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

年代:1993

数据来源: WILEY

摘要:

AbstractThe 2‐connected Steiner subgraph problem is that of finding a minimum‐weight 2‐connected subgraph that spans a subset of distinguished vertices. This paper presents linear‐time algorithms for solving the 2‐connected Steiner subgraph problem on two special classes of graphs,W4‐free graphs and Halin graphs. Although different in detail, the algorithms adopt a common strategy exploiting known decompositions. As a special case, the algorithms also solve the Traveling Salesman Problem onW4‐free graphs and Halin graphs. ©1993 by John W

ISSN:0028-3045    

DOI:10.1002/net.3230230307

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

年代:1993

数据来源: WILEY

摘要:

AbstractGiving a partial solution to a conjecture of Balas and Yu [Networks19(1989) 247–235], we prove that if the complement of a graphGonnvertices contains no set oft+ 1 pairwise disjoint edges as an induced subgraph, thenGhas fewer than (n/2t)2tmaximal complete subgraphs. ©1993 by John Wiley&Sons, I

ISSN:0028-3045    

DOI:10.1002/net.3230230308

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

年代:1993

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230230301

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

年代:1993

数据来源: WILEY