Cloning, expression, and evolutionary analysis of α-gliadin genes from em class=a-plus-plusTriticumem and em class=a-plus-plusAegilopsem genomes.pdfVIP

Approximation Algorithms for the Bottleneck Stretch Factor Problem Giri Narasimhan and Michiel Smid Department of Mathematical Sciences, The University of Memphis, Memphis TN 38152 giri@msci.memphis.edu Department of Computer Science, University of Magdeburg, Magdeburg, Germany michiel@isg.cs.uni-magdeburg.de 1 Introduction Assume that we are given the coordinates of airports. Given an airplane that can fly a distance of miles without refueling, a typical query is to determine the smallest value of such that the airplane can travel between any pair of airports using flight segments of length at most miles, such that the sum of the lengths of the flight segments is not longer than times the direct “as-the-crow-flies” distance between the airports. This problem falls under the general category of bottleneck problems. In our case, the stretch factor , i.e., the value of , is a measure of the maximum increase in fuel costs caused by choosing a path other than the direct path between any source and any destination. (Clearly, this direct path cannot be taken if its length is larger than miles.) Let us formalize this problem. For simplicity, we take the Euclidean metric for the distance between two airports. In practice, one needs to take into account the curvature of the earth and the wind conditions. Let be a small constant. For any two points and in , we denote their Euclidean distance by . Let be a set of points in , and let be an undirected graph having as its vertex set. The length of any edge of is defined as . Furthermore, the length of any path in between two vertices and is defined as the sum of the lengths of the edges on this path. We call such a graph a Euclidean graph . For any two vertices and of , we denote by their distance in , i.e., the length of