摘要:

AbstractThis paper formulates and classifies some multicommodity flow problems (MFP) on “stochastic networks.” Here, the arc attributes are not necessarily deterministic, but, rather, are allowed to be probabilistic. Some special cases of the stochastic multicommodity flow problems (SMFP) are considered where the resultant formulations are solvable by existing algorithms for MFP. Specifically, we consider the following problems:(1)SMFP‐FLOW INDEPENDENT, where the arc travel attributes are random but not dependent on the flows in the network, and(2)SMFP‐FLOW DEPENDENT, where the stochasticity of arc travel attributes is either due to random demands or due to arc free‐flow travel attributes being probabilistic.The scenario where the cost functionc(w), of travel attributew, is linear is fully explored‐for both the above problems. Also, some special cases of the problems are studied whenc(w)is exponential or quadratic inw. As an illustrative application, some traffic assignment problems on stochastic networks are formulated and solv

ISSN:0028-3045    

DOI:10.1002/net.3230200202

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

年代:1990

数据来源: WILEY

摘要:

AbstractLetF= {I1,I2,…,In} be a finite family of closed intervals on the real line. Two intervalsIjandIkinFare said to overlap each other if they intersect but neither one of them contains the other. A graphG= (V,E) is called an overlap graph forFif there is a one‐to‐one correspondence betweenVandFsuch that two vertices inVare adjacent to each other if and only if the corresponding intervals inFoverlap each other. In this paper, we present two efficient algorithms for finding maximum cliques of an overlap graph when it is given in the form of a family ofnintervals. The first algorithm finds a maximum clique inO(n. logn+Min{m, n‐ ω}) time, wheremis the number of edges and ω is the size of a maximum clique, respectively, of the graph. The second algorithm generates all maximum cliques inO(n‐ logn+m+ γ) time, where γ is the total sum o

ISSN:0028-3045    

DOI:10.1002/net.3230200203

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

年代:1990

数据来源: WILEY

摘要:

AbstractThe problem under consideration arises from studies on local networks and multimodule memory organizations. The ring network has been one of the popular network topologies used in the design and implementation of local area networks and other configurations. We consider here a generalization of the ring network by adding two fixed‐step links to each node. The resulting networks have low diameter, easy routing, and switching structure and therefore are suitable for implementation in the design of reliable networks. LetNdenote the number of nodes in the network. For a givenN, we are concerned with the problem of determining the best topologies to minimize the diameter (and, hence, the transmission delay) of the network. We obtain new classes of values ofNfor which topologies can be found that achieve the lower boundlb= [(√2N‐ 1 ‐ 1)/2] for the minimum diameter. We also show that for some infinite classes ofNthis lower boundlbis not ach

ISSN:0028-3045    

DOI:10.1002/net.3230200204

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

年代:1990

数据来源: WILEY

摘要:

AbstractThis paper considers the problem of partitioning the nodes of a weighted graph intokdisjoint subsets of bounded size, such that the sum of the weights of the edges whose end vertices belong to the same subset is maximized. A class of approximation algorithms based on matching is presented. These algorithms are shown to yield practical worst‐case bounds whenkis large. Extensive empirical experimentation indicates that the methods produce consistently good solutions to an important VLSI design problem in a fraction of the time required by competing method

ISSN:0028-3045    

DOI:10.1002/net.3230200205

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

年代:1990

数据来源: WILEY

摘要:

AbstractWe consider the location problem of an obnoxious facility with respect to a finite number of inhabitants, where the inhabitants have specified locations at vertices of a networkN. A voting solution, called anti‐Condorcet point, is defined as a point ofNsuch that no other point is farther from a strict majority of inhabitants. On a general network with an odd number of inhabitants, it is shown that there exists a finite set of points that contains all such solutions. An example shows that this result does not directly extend to an even number of inhabitants on a general network. In the special case of a tree network, one of the extreme vertices of a diameter is an anti‐Condorcet point, and a linear algorithm for finding it is presented. Finally, a bound on the maximum decrease of the total distance to the inhabitants is provided when an anti‐Condorcet point is preferred to a “maxisum”

ISSN:0028-3045    

DOI:10.1002/net.3230200206

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

年代:1990

数据来源: WILEY

摘要:

AbstractWe consider two cost allocation problems that arise when the prospective users of a communication network seek a fair method for allocating the cost of constructing the network. We assume the network is of minimum cost and its edge capacities are large enough to satisfy requirements for every pair of users. If the requirements are time‐invariant and have to be satisfied simultaneously, the problem of finding a minimum‐cost network is called thesimultaneous network synthesis problem, whereas if the requirements can be satisfied for one pair of users at a time, it is called the nonsimultaneous network synthesis problem. We formulate the cost allocation problems arising from the above problems as cooperative games, referred to as the simultaneous and the nonsimultaneous network synthesis games. We prove that both the (equal cost) nonsimultaneous and the simultaneous network synthesis games are convex and provide nonredundant representations of their cores. For the simultaneous network synthesis game, we present a closed‐form expression for the nucleolus and prove that it coincides with the Shapley value. For the (equal cost) nonsimultaneous network synthesis game, we, provide a closed‐form expression for the nucleolus when the requirement structure is tree‐shaped and develop a quadratic time algorithm for computing the Shapley value in

ISSN:0028-3045    

DOI:10.1002/net.3230200207

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

年代:1990

数据来源: WILEY

摘要:

AbstractThe algorithm presented here makes exact computations of characteristics of the probability distribution of project duration for a stochastic project network. Given discrete independent probability distributions for task durations, the algorithm will compute either moments of the project duration distribution or values of the cumulative distribution function of project duration. The algorithm can be used for sensitivity analysis on probability weights since several task duration distributions having the same range can be handled simultaneously with no great increase in computation time requirements.

ISSN:0028-3045    

DOI:10.1002/net.3230200208

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

年代:1990

数据来源: WILEY

ISSN:0028-3045    

DOI:10.1002/net.3230200201

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

年代:1990

数据来源: WILEY