Search

Abstract: A ring star in a graph is a subgraph that can be decomposed into a cycle (or ring) and a set of edges with exactly one vertex in the cycle. In the minimum ring-star problem (mrsp) the cost of a ring star is given by the sum of the costs of its edges, which vary, depending on whether the edge is part of the ring or not. The goal is to find a ring-star spanning subgraph minimizing the sum of all ring and assignment costs. In this paper we show that the mrsp can be reduced to a minimum (constrained) Steiner arborescence problem on a layered graph. This reduction is used to introduce a new integer programming formulation for the mrsp. We prove that the dual bound generated by the linear relaxation of this formulation always dominates the one provided by an early model from the literature. Based on our new formulation, we developed a branch-and-cut algorithm for the mrsp. On the primal side, we devised a grasp heuristic to generate good upper bounds for the problem. Computational tests with these algorithms were conducted on a benchmark of public domain. In these experiments both our exact and heuristics algorithms had excellent performances, noticeably in dealing with instances whose optimal solution has few vertices in the ring. In addition, we also investigate the minimum spanning caterpillar problem (mscp) which has the same input as the mrsp and admits feasible solutions that can be viewed as ring stars with paths in the place of rings. We present an easy reduction of the mscp to the mrsp, which makes it possible to solve to optimality instances of the former problem too. Experiments carried out with the mscp revealed that our branch-and-cut algorithm is capable to solve to optimality instances with up to 200 vertices in reasonable time. [Copyright &y& Elsevier]

Abstract: Let be a connected graph with vertices. Let be an integer. Suppose that a fire breaks out at a vertex of . A firefighter starts to protect vertices. At each time interval, the firefighter protects -vertices not yet on fire. At the end of each time interval, the fire spreads to all the unprotected vertices that have a neighbour on fire. Let sn denote the maximum number of vertices in that the firefighter can save when a fire breaks out at vertex . The -surviving rate of is defined to be , which is the average proportion of saved vertices. In this paper, we investigate the surviving rate of outerplanar graphs with vertices. The main results are as follows: (1) ; and (2) if , and if , which improves the result in [L.Cai, W.Wang, The surviving rate of a graph for the firefighter problem, SIAM J. Discrete Math. 23 (2009) 1814–1826]. [ABSTRACT FROM AUTHOR]

Abstract: In a capacitated graph with a set of commodities, the sparsity of a cut is the ratio between the capacity of the cut and the demand of the commodities separated by the cut. The Sparsest Cut (SC) is often introduced as a weak dual of the Maximum Concurrent Flow problem (MCF). Contrarily to MCF, problem SC is, in general, NP-hard. This problem has been considerably studied, motivating the design of very elaborated approximation algorithms [Auman, Y. and Y. Rabani, Approximate min-cut max-flow theorem and approximations algorithm, SIAM Journal on Computing 27 (1998), pp. 213–238] [Günlük, O., On the min-cut max-flow ratio for multicommodity flows, SIAMJ. of Disc. Math. 21 (2007), pp. 1–15] [N. Garg, M. Y., V. Vazirani, Approximate max-flow min-(multi)cut theorems and their applications, in: STOC''93, 1993, pp. 698–707] [S. Plotkin, E. T., Improved bounds on the max-flow min-cut ratio for multicommodity flows, in: 25th Symposium on Theory of Computing, 1993] [Tragoudas, S., Improved approximations for the min-cut max-flow ratio and the flux, Mathematical Systems Theory 29 (1996), pp. 157–167]. Somewhat surprisingly, to the best of our knowledge, problem (SC) has not been investigated with exact approaches using Mixed Integer Programming models. In this paper, we propose a formulation arising “naturally” from the dual of (MCF). [Copyright &y& Elsevier]

Abstract: A spanning caterpillar in a graph is a tree composed by a path such that all vertices not in the path are leaves. In the Minimum Spanning Caterpillar Problem (MSCP) each edge has two costs: a path cost when it belongs to the path and a connection cost when it is incident to a leaf. The goal is to find a spanning caterpillar minimizing the sum of all path and connection costs. In this paper we formulate the as a minimum Steiner arborescence problem. This reduction is the basis for the development of an efficient branch-and-cut algorithm for the MSCP. We als developed a GRASP heuristic to generate primal bounds. Experiments carried out on instances adapted from TSPLIB 2.1 revealed that the exact algorithm is capable to solve to optimality instances with up to 300 vertices in reasonable time. They also showed that our heuristic yields very high quality solutions. [Copyright &y& Elsevier]

Abstract: In this paper we develop a network location model that combines the characteristics of ordered median and gradual cover models resulting in the Ordered Gradual Covering Location Problem (OGCLP). The Gradual Cover Location Problem (GCLP) was specifically designed to extend the basic cover objective to capture sensitivity with respect to absolute travel distance. The Ordered Median Location problem is a generalization of most of the classical locations problems like -median or -center problems. The OGCLP model provides a unifying structure for the standard location models and allows us to develop objectives sensitive to both relative and absolute customer-to-facility distances. We derive Finite Dominating Sets (FDS) for the one facility case of the OGCLP. Moreover, we present efficient algorithms for determining the FDS and also discuss the conditional case where a certain number of facilities is already assumed to exist and one new facility is to be added. For the multi-facility case we are able to identify a finite set of potential facility locations a priori, which essentially converts the network location model into its discrete counterpart. For the multi-facility discrete OGCLP we discuss several Integer Programming formulations and give computational results. [Copyright &y& Elsevier]

Abstract: Let be a graph without isolated vertices. For a positive integer , a set is a -distance paired-dominating set if each vertex in is within distance of a vertex in and the subgraph induced by contains a perfect matching. In this paper, we present two linear time algorithms to find a minimum cardinality -distance paired-dominating set in interval graphs and block graphs, which are two subclasses of chordal graphs. In addition, we present a characterization of trees with unique minimum -distance paired-dominating set. [Copyright &y& Elsevier]

Abstract: We consider the edge-partition problem, which is a graph theoretic problem arising in the design of Synchronous Optical Networks. The deterministic edge-partition problem considers an undirected graph with weighted edges, and simultaneously assigns nodes and edges to subgraphs such that each edge appears in exactly one subgraph, and such that no edge is assigned to a subgraph unless both of its incident nodes are also assigned to that subgraph. Additionally, there are limitations on the number of nodes and on the sum of edge weights that can be assigned to each subgraph. In this paper, we consider a stochastic version of the edge-partition problem in which we assign nodes to subgraphs in a first stage, realize a set of edge weights from a finite set of alternatives, and then assign edges to subgraphs. We first prescribe a two-stage cutting plane approach with integer variables in both stages, and examine computational difficulties associated with the proposed cutting planes. As an alternative, we prescribe a hybrid integer programming/constraint programming algorithm capable of solving a suite of test instances within practical computational limits. [Copyright &y& Elsevier]