A framework and algorithms for circular drawings of graphs

In this paper, we present a framework and two linear time algorithms for obtaining circular drawings of graphs. The first technique produces circular drawings of biconnected graphs and finds a zero crossing circular drawing if one exists. The second technique finds multiple embedding circle drawings. Techniques for the reduction of edge crossings are also discussed. Results of experimental studies are included.     

Extending the stochastic programming framework for the modeling of several decision makers: pricing and competition in the telecommunication sector

In a previous paper, Gouveia and Magnanti (2003) found diameter-constrained minimal spanning and Steiner tree problems to be more difficult to solve when the tree diameter D is odd. In this paper, we provide an alternate modeling approach that views problems with odd diameters as the superposition of two problems with even diameters. We show how to tighten the resulting formulation to develop a model with a stronger linear programming relaxation. The linear programming gaps for the tightened model are very small, typically less than 0.5–, and are usually one third to one tenth of the gaps of the best previous model described in Gouveia and Magnanti (2003). Moreover, the new model permits us to solve large Euclidean problem instances that are not solvable by prior approaches. Research funded in part by the Research Projects POCTI-ISFL-1-152,POSI/CPS/41459/2001 and POCTI/MAT/139/94 Research funded in part by the Singapore-MITAlliance(SMA)     

Variations on the Theorem of Birkhoff – von Neumann and Extensions

 The theorem of Birkhoff – von Neumann concerns bistochastic matrices (i.e., matrices with nonnegative real entries such that all row sums and all column sums are equal to one). We consider here real matrices with entries unrestricted in sign and we extend the notion of permutation matrices (integral bistochastic matrices); some generalizations of the theorem are derived by using elementary properties of graph theory. Received: October 10, 2000 Final version received: April 11, 2002     

Network reinforcement

We give an algorithm for the following problem: given a graph G=(V,E) with edge-weights and a nonnegative integer k, find a minimum cost set of edges that contains k disjoint spanning trees. This also solves the following reinforcement problem: given a network, a number k and a set of candidate edges, each of them with an associated cost, find a minimum cost set of candidate edges to be added to the network so it contains k disjoint spanning trees. The number k is seen as a measure of the invulnerability of a network. Our algorithm has the same asymptotic complexity as |V| applications of the minimum cut algorithm of Goldberg & Tarjan. Received: April, 2004     

Survivable networks,linear programming relaxations and the parsimonious property

We consider the survivable network design problem — the problem of designing, at minimum cost, a network with edge-connectivity requirements. As special cases, this problem encompasses the Steiner tree problem, the traveling salesman problem and thek-edge-connected network design problem. We establish a property, referred to as the parsimonious property, of the linear programming (LP) relaxation of a classical formulation for the problem. The parsimonious property has numerous consequences. For example, we derive various structural properties of these LP relaxations, we present some algorithmic improvements and we perform tight worst-case analyses of two heuristics for the survivable network design problem.The research of both authors was partially supported by the National Science Foundation under grant ECS-8717970 and the Leaders for manufacturing program at MIT.     

基于Petri Net的需求流动网组建模型及其稳定性分析

针对供应链概念不足,提出需求流动网概念,并论述了需求流动网概念模型,运用Petri网理论建立需求流动网模型,并对模型进行了分析,随后在分析需求流动网稳定性内涵的基础上,进一步运用Petri网理论分析了需求流动网稳定性,并最终得出了相应结论.     

Sequential location-allocation problems on chains and trees with probabilistic link demands

In this paper, we consider multiperiod minisum location problems on networks in which demands can occur continuously on links according to a uniform probability density function. In addition, demands may change dynamically over time periods and at most one facility can be located per time period. Two types of networks are considered in conjunction with three behavioral strategies. The first type of network discussed is a chain graph. A myopic strategy and long-range strategy for locatingp-facilities are considered, as is a discounted present worth strategy for locating two facilities. Although these problems are generally nonconvex, effective methods are developed to readily identify all local and global minima. This analysis forms the basis for similar problems on tree graphs. In particular, we construct algorithms for the 3-facility myopic problem and the 2-facility long-range and discounted cost problems on a tree graph. Extensions and suggestions for further research on problems involving more general networks are provided.     

Fuzzy network technique for technological forecasting

The stochastic network technique is known to be a powerful tool carrying out a technological forecast of complex systems. A network dealt with is characterized by a tetrad of essential elements: logical nodes with some inputs and outputs, probabilistics activity branches, feedback loops, and multiple sources and sinks. A set of network parameters is defined for each element and their values are estimated for practical analysis of the network. In the case where the system to be treated is very large and/or complex, it cannot always be represented by a definite network and therefore forecasted values of parameters are inevitably indefinite themselves. A conventional probabilistic approach is sometimes inadequate in such a case. In the light of these facts, the paper proposes a fuzzy network technique, in which among activity branches emanating from a node, a branch to be undertaken once the node is realized belongs to a fuzzy set; and the time required to complete an activity branch belongs to a fuzzy set. Operations of maximum and minimum for sum and product of fuzzy sets take the place of manipulations of addition and multiplication for probabilities, respectively. Although the operations are somewhat formal, the obtained results seem interesting. A numerical example is attached to show a comparison of the proposed technique with the conventional one.     

The biobjective absolute center problem

This paper deals with the problem of determining the absolute center of a network, taking into account two objective functions. These functions consist of minimizing the maximum of the distances from any point on the network to the vertices, using two independent lengths on each edge. We propose an algorithm in polynomial time to obtain the non-dominated location points on the network, using the Kariv and Hakimi method (1979). This work was partially supported by project number 93/108 from the Dirección General de Universidades e Investigación del Gobierno de Canarias.