摘要:

AbstractThe problem of embedding an undirected graph on the planar grid is considered. Two common cost measures for this sort of problem are the area consumed by the embedding and the total length of edges in the embedding. This paper considers a third cost measure, called thenode cost measure, which is the total number of bends that are present along edges of the embedding. The node cost measure has applications to light or microwave circuits where it requires a separate device each time a corner is turned. In addition, this problem has limited applications to traditional circuit and VLSI layout. Although it is shown that finding a minimal node‐code embedding is in general an NP‐complete problem, three good approximation strategies are given along with worst‐case bounds on their performance; one of the strategies is shown to be nearly optimal for a large class of g

ISSN:0028-3045    

DOI:10.1002/net.3230140202

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

年代:1984

数据来源: WILEY

摘要:

AbstractA necessary condition for synthesis of multicommodity flow networks is derived. The feasible flow region of a multicommodity flow network is shown to be an antiblocking polyhedron with rational slopes. Also, it is established that this condition is sufficient for two‐commodity flow networks. A synthesis algorithm for two‐commodity flow networks is proposed. The size of the resulting networks is studied and for some regions it is shown to be pseudolinear; in the worst case the network found by the algorithm is optimal to within a constant fac

ISSN:0028-3045    

DOI:10.1002/net.3230140203

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

年代:1984

数据来源: WILEY

摘要:

AbstractOkamura and Seymour recently proved two properties of multicommodity flows in undirected planar networks where all the sources and the sinks are on a common face of the underlying graph. One is that a feasible solution is guaranteed whenever each cut's capacity is at least as large as the cut's demand. The second is that if all demands and capacities are integers then the flow values may be chosen half‐integer‐valued. In this paper we use the first property to construct two computational procedures; one examines the existence of a feasible flow, and the other constructs such a flow if one exists. We also show that the construction procedure can be used as an alternative proof to the above properties. Finally we show, by presenting counterexamples, that the half‐integrality property does not necessarily hold when either the graph cannot be drawn in the plane with all sources and sinks on a common face, or the graph is dir

ISSN:0028-3045    

DOI:10.1002/net.3230140204

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

年代:1984

数据来源: WILEY

摘要:

AbstractIn this paper we present heuristic algorithms for the period vehicle routing problem, the problem of designing vehicle routes to meet required service levels for customers and minimize distribution costs over a given several‐day period of time. These heuristic algorithms are based on an initial choice of customer delivery days which meet the service level requirements, followed by an interchange procedure in an attempt to minimize distribution costs. The heuristic algorithms represent distribution costs by replacing the vehicle routing problem for each day of the period by (i) a median problem and (ii) a traveling salesman problem. Computational results and comparisons are given for the algorithms, based on test problems derived from the literature with up to 126 customers. The largest of these problems is the one given and solved by Russell and Igo. The solution obtained for this problem by the heuristic algorithms shows an improvement of 13% over the previous best solutio

ISSN:0028-3045    

DOI:10.1002/net.3230140205

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

年代:1984

数据来源: WILEY

摘要:

AbstractWe present a new unified approach for shortest‐path problems. Based on this approach, we develop a computational method which consists of determining shortest paths on a finite sequence of partial graphs defined as the “growth of the original graph.” We show that the proposed method allows us to interpret within the same framework several different well‐known algorithms, such as those of D′Esopo‐Pape, Dijkstra, and Dial, and leads to a uniform analysis of their computational complexity. We also stress the existing parallelism between the proposed method and the matrix‐multiplication methods of Floyd‐Warsha

ISSN:0028-3045    

DOI:10.1002/net.3230140206

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

年代:1984

数据来源: WILEY

摘要:

AbstractThis article presents two sorting procedures with computational complexityO(nk2log(k)) andO(nk2) to perform the generalized vector productA1⊗A2⊗ ⃛ ⊗An, where each vectorAihaskdistinct elements arranged in strictly increasing order. The vector product identifies thekminimal sums, each sum being defined as having one addend from each

ISSN:0028-3045    

DOI:10.1002/net.3230140207

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

年代:1984

数据来源: WILEY

摘要:

AbstractWe have evolved a classification scheme to characterize algorithms for solving shortestpath problems. The algorithms are classified according to (A) the problem type, i.e., the question being asked about the given network; (B) the input type, i.e., the salient features of the given network which impact on the design of the algorithm and selection of data structures; and (C) the type of underlying technique employed to solve the problem. An annotated bibliography of 79 selected references on shortest‐path algorithms is included. We have also provided a more complete listing of 222 references carefully culled out of a larger body of literature on shortest‐path algorithms through the year 1

ISSN:0028-3045    

DOI:10.1002/net.3230140208

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

年代:1984

数据来源: WILEY

摘要:

AbstractLetGbe a directed graph containingnvertices, one of which is a distinguished sources, andmedges, each with a non‐negative cost. We consider the problem of finding, for each possible sink vertexv, a pair of edge‐disjoint paths fromstovof minimum total edge cost. Suurballe has given anO(n2logn)‐time algorithm for this problem. We give an implementation of Suurballe's algorithm that runs inO(mlog(1+ m/n)n) time andO(m) space. Our algorithm builds an implicit representation of thenpairs of paths; given this representation, the time necessary to explicitly construct the pair of paths for any given sink isO(1) per edge on the

ISSN:0028-3045    

DOI:10.1002/net.3230140209

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

年代:1984

数据来源: WILEY

摘要:

AbstractWe solve in this paper a problem proposed by Bi‐weng Zhu at the First Combinatorics and Graph Theory Conference of China. For the minimum degree δ, connectivity k, and line‐connectivity λ of a (p,q) graph,p,qfixed, the maximum values of δ ‐ k, δ ‐ λ, and λ ‐ k are given as well as extremal graphs for which these upper boun

ISSN:0028-3045    

DOI:10.1002/net.3230140210

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

年代:1984

数据来源: WILEY

摘要:

AbstractIn this paper methods are described that will compute the edge‐connectivity of a graph or a digraph at least twice as fast as the known methods. A study of the computation of the vertex‐connectivity is presented which leads to new algorithms for this purpose or for the purpose of determining if the vertex‐connectivity is at leastk. These algorithms compare favorably with Kleitman's, Even's, Even and Tarjan's, and Galil's algor

ISSN:0028-3045    

DOI:10.1002/net.3230140211

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

年代:1984

数据来源: WILEY