摘要:

AbstractThe general Node‐Weighted Steiner Tree problem is an extension of the standard Steiner Tree problem by the addition of node‐associated weights. This article analyzes a special case of that problem, where the set of nodes, which must be included in the solution tree, consists of a single node, and all node weights are negative. The special case is shown to be NP‐Complete, its integer programming formulation is presented, and heuristic procedures are proposed. Using Lagrangian relaxation and subgradient optimization, tight lower bounds were derived and utilized by a branch and bound algorithm. The effectiveness of the developed procedures is demonstrated by a set of computational experi

ISSN:0028-3045    

DOI:10.1002/net.3230170102

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

年代:1987

数据来源: WILEY

摘要:

AbstractThe problem of compacting a programmable logic array is formulated as the following graph problem. Given a red‐edge bipartite graph, how to add maximum number of independent green edges such that there are no cycles formed by alternating red and green edges. For this NP‐complete problem, we present a polynomial heuristic algorithm which gives an optimum solution when the red bipartite graph satisfies certain conditions, e.g., a tree. When the bipartite graph does not satisfy these conditions, the heuristic algorithm gives a solution with worst‐case error bound. For a red bipartite graph with given cardinality, we give a tight upper bound on the number of green

ISSN:0028-3045    

DOI:10.1002/net.3230170103

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

年代:1987

数据来源: WILEY

摘要:

AbstractA linear diforest is a digraph whose connected components are paths. We define the linear arboricity of a digraph, denotedla(G), as the minimum number of linear diforests which partition the arcs ofG.In this paper, we prove that the determination ofla(G)is NP‐complete. We prove also that the problem becomes polynomial for acyclic digraphs. Finally, we give the value ofla(G)for several families of digraphs, in particular 2‐regular digra

ISSN:0028-3045    

DOI:10.1002/net.3230170104

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

年代:1987

数据来源: WILEY

摘要:

AbstractLocating‐dominating sets are of interest in safeguard applications of graphical models of facilities. A subsetSof the vertex setVof a graphGis a dominating set if each vertexu ϵ V ‐ Sis adjacent to at least one vertex inS.For eachvinV ‐ SletS(v)denote the set of vertices inSwhich are adjacent tov.A dominating setSis defined to be “locating” if for any two verticesvandwinV ‐ Sone hasS(v)≠S(w). Sharp bounds on the cardinality of locating‐dominating sets for arbitrary graphs onpvertices and for trees onpvertices are given, and a linear (that isO(P))algorithm for finding a minimum cardinality locating‐dominating set in an acyclic

ISSN:0028-3045    

DOI:10.1002/net.3230170105

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

年代:1987

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230170106

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

年代:1987

数据来源: WILEY

摘要:

AbstractThe Steiner network problem seeks a minimum weight connected subgraph that spans a specified subset off nodes in a given graph and optionally uses any of the other nodes as intermediate or Steiner points. This model has a variety of practical applications particularly in location, transportation, and communication planning. In this paper, we first outline some distinctive characteristics of optimal Steiner network solutions and propose a problem reduction procedure based on these properties. We derive a conservative estimate of the expected reduction achieved by this method under one set of probabilistic assumptions and demonstrate that this scheme produces asymptotically optimal reduction. We also report computational results for several randomly generated test problems. We then devise a tree generation algorithm that exploits the special structure of the Steiner network problem while solving its constrained minimal spanning tree formulation.

ISSN:0028-3045    

DOI:10.1002/net.3230170107

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

年代:1987

数据来源: WILEY

摘要:

AbstractConsider a network with arcs subject to failures. We show how the problem of investing in new arcs in such a network in order to increase the expected max flow as much as possible can be formulated as a stochastic program with network recourse. We show how to decompose the problem, and consider both exact methods and approximations. Convergence proofs are given. We demonstrate that max flow recourse problems can be solved very efficiently, since lower and upper bounds are equally simple to evaluate.

ISSN:0028-3045    

DOI:10.1002/net.3230170108

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

年代:1987

数据来源: WILEY

摘要:

AbstractSeries‐parallel graphs, outerplanar graphs, and graphs whose polygon matroids are transversal have been characterized by forbidden subgraphs. Tutte introduced a graph decomposition for nonseparable graphs. The results of this paper relate the existence of the forbidden subgraphs to properties of the decomposition. Algorithmic implications are considere

ISSN:0028-3045    

DOI:10.1002/net.3230170109

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

年代:1987

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230170101

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

年代:1987

数据来源: WILEY