摘要:

AbstractIn this paper, we consider a special case of the time‐dependent traveling salesman problem where the objective is to minimize the sum of all distances traveled from the origin to all other cities. Two exact algorithms, incorporating lower bounds provided by a Lagrangean relaxation of the problem, are presented. We also investigate a heuristic procedure derived from dynamic programming that is able to evaluate the distance from optimality of the produced solution. Computational results for a number of problems ranging from 15 to 60 cities are given. They show that problems up to 35 cities can be solved exactly and problems up to 60 cities can be solved within 3% from optimality. ©1993 by John Wiley&Sons, I

ISSN:0028-3045    

DOI:10.1002/net.3230230202

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

年代:1993

数据来源: WILEY

摘要:

AbstractA graph‐theoretical model is presented for scheduling the transmission of messages in a computer network. A related wiring problem is also discussed; connections with classical edge colorings are exhibited and optimality properties are discussed. ©1993 by John Wiley&Sons, I

ISSN:0028-3045    

DOI:10.1002/net.3230230203

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

年代:1993

数据来源: WILEY

摘要:

AbstractWe consider graphsG = (V,E)with order ρ = |V|, sizee= |E|, and stability number β0. We collect or determine upper and lower bounds on each of these parameters expressed as functions of the two others. We prove that all these bounds are sharp. ©1993 by John Wiley&Sons, I

ISSN:0028-3045    

DOI:10.1002/net.3230230204

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

年代:1993

数据来源: WILEY

摘要:

AbstractWe study a specialized version of network design problems that arise in telecommunications, transportation, and other industries. The problem, a generalization of the shortest path problem, is defined on an undirected network consisting of a set of arcs on which we can install (load), at a cost, a choice of up to three types of capacitated facilities. Our objective is to determine the configuration of facilities to load on each arc that will satisfy the demand of a single commodity at the lowest possible cost. Our results (i) demonstrate that the single‐facility loading problem and certain “common break‐even point” versions of the two‐facility and three‐facility loading problems are polynomially solvable as a shortest path problem; (ii) show that versions of the two‐facility loading problem are strongly NP‐hard, but that a shortest path solution provides an asymptotically “good” heuristic; and (iii) characterize the optimal solution (i.e., specify a linear programming formulation with integer solutions) of the common break‐even point versions of the two‐facility and three‐facility loading problems. In this development, we introduce two new families of facets, give geometric interpretations of our results, and demonstrate the usefulness of partitioning the space of the problem parameters to establish polyhedral integrality properties. Generalizations of our results apply to (i) multicommodity applications and (ii) situations with more than three facilities. ©19

ISSN:0028-3045    

DOI:10.1002/net.3230230205

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

年代:1993

数据来源: WILEY

摘要:

AbstractAt‐spanner of a network is a subnetwork in which every two nodes that were connected by an edge in the original network are connected by a path of at mosttedges in the subnetwork. We presentt‐spanners with small maximum or average degree for multidimensional grids. We show how to construct small maximum degree 3‐spanners ford‐dimensional grids ford© 2 and constant average degree 3‐spanners ford‐dimensional grids. We also presentt‐spanners of minimum average degree for 2‐dimensional grids. ©1993 by Joh

ISSN:0028-3045    

DOI:10.1002/net.3230230206

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

年代:1993

数据来源: WILEY

摘要:

AbstractA graph or multigraphG* isk‐edge fault‐tolerant with respect to a graphG, denotedk‐EFT(G), if every graph obtained by removing anykedges fromG* containsG. We observe that forksufficiently large ak‐EFT(G)graph must be a multigraph, and we present some basic conditions that such multigraphs must meet. We then study the problem of constructingk‐EFT(G)graphs that are optimal in that they contain the minimum number of edges among allk‐EFT(G)graphs. Families of optimalk‐EFT(G)graphs, whereGis then‐node path or cycle, are presented for allkandn. We also give an optimal 1‐EFT design for then‐dimensional hypercube. ©1993 by

ISSN:0028-3045    

DOI:10.1002/net.3230230207

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

年代:1993

数据来源: WILEY

摘要:

AbstractWe prove that the single‐source uncapacitated (SSU) version of the concave cost network flow problem, when all arcs except one have linear cost, is in the classPof problems solvable in time polynomial in the problem input length. This contrasts the corresponding result without network constraints, in which the problem is known to be NP‐hard [6]. ©1993 by John Wiley&Sons,

ISSN:0028-3045    

DOI:10.1002/net.3230230208

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

年代:1993

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230230209

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

年代:1993

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230230201

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

年代:1993

数据来源: WILEY