A network is a system that involves movement or flow of some commodities such as goods and services. In fact any structure that is in the form of a system of components some of which interact can be considered as a network. In network design the problem is often to construct economical and reliable networks which satisfy certain requirements and which are optimal according to some criterion such as cost, output or performance. Graph theory is useful when the requirements of the network can be expressed in terms of graph parameters, usually as bounds. Some of the graph parameters that have been considered include: degree; distance; diameter; and connectivity. Problems with these parameter restrictions are usually from a class of NP-complete problems with instances that require exponential computer time to solve by available algorithms.The major focus of this thesis is to develop fast and efficient heuristics for some of these NP-complete problems. The two main topics analysed are Restricted Spanning Trees and Graph Partitioning. The aim of the Restricted Spanning Trees section is to construct the most efficient spanning tree (connected network) subject to various degree constraints. These degree constraints imposed are usually in the form of an upper bound. The upper bound represents the maximum number of connections allowed on a particular vertex. The Graph Partitioning section considers the problem of clustering vertices of the graph into sets such that the overall cost of the edges in the different sets is minimised.Chapter 1 provides the notation and terminology used throughout the thesis and a review and summary of the thesis.A literature review of related work that has been carried out to date is presented in Chapter 2. Some of the more promising results are discussed. The first part of the chapter surveys work related to the Restricted Spanning Tree problem. ++ / Analysis of both exact and heuristic methods is given. The second part of Chapter 2 provides a survey of the Graph Partitioning problem. We discuss the many different approaches that have been proposed to solve this problem. The quality of computational results achieved is discussed.Chapter 3 considers the Degree Constraint Minimum Weight Spanning Tree problem. This problem arises in networks where a given terminal is only allowed connections to a maximum number of specified terminals. We consider a number of cases including: same degree constraint on each vertex; different degree constraint on some vertices; and when the degree constraint is only on one or two vertices. A number of heuristics are developed and implemented and compared against an exact Branch and Cut algorithm. Our computational results demonstrated the value of our better performing heuristics.Chapter 4 considers the complexity of the (1,k)-tree problem. This problem is defined m given a graph G with maximum degree k find a spanning tree T with all vertices having degree 1 or k. Analysis is done on graphs with maximum degree 3, 4 and 5. Results establishing that the (1,3)-tree and (1, 4)-tree problems are NP-complete are presented. Further consideration is also given to the complexity of spanning trees with degree from the set { 1, 3, 5}. Analysis is also carried out on the number of degree one vertices in the (1, k)-tree. Presentation of heuristic procedures to solve this NP-complete problem concludes the chapter.Chapter 5 is devoted to the Graph Partitioning problem. A number of heuristics are presented and extensive computational work carried out. Computational findings support the usefulness of the heuristic methods both in terms of quality and time.We conclude this thesis by detailing some future work that can be carried out.

No description available.

No description available.

Made available in DSpace on 2014-06-12T15:55:53Z (GMT). No. of bitstreams: 2 arquivo2330_1.pdf: 3127189 bytes, checksum: 01d7c49fae931bcb459bfda7372af32e (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2009 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / A solução de problemas complexos em várias áreas do conhecimento humano, tais como: análise de investimento no setor bancário, análise e visualização de imagens médicas em tempo real, indústria de óleo e gás, etc. que utilizam muitas vezes algoritmos complexos e/ou uma grande massa de dados, têm requerido cada vez mais sistemas computacionais de alto desempenho para seu processamento. Estes aplicativos, em sua maioria, devido a sua grande massa de dados, grandes laços de processamento em seus procedimentos, podem consumir dias ou até meses de trabalho, em computadores de processamento seqüencial, para apresentar o resultado final. Existem casos em que este tempo excessivo pode inviabilizar um projeto em questão, por perder o time to market de um produto. Diferentes tecnologias e estruturas de dados têm sido sugeridas para lidar com tais problemas, visando uma melhor customização, tentando retirar o melhor da arquitetura e do sistema, seja em termos de software como de hardware. Dentre estas arquiteturas hw/sw, optamos neste trabalho ao estudo de uma solução baseada em FPGAs (Field Programmable Gate Arrays) como um co-processador. O uso deste dispositivo permite uma nova abordagem do problema. Agora, um determinado aplicativo poderia ser particionado em duas partes: a primeira, aquela com características de controle, processo seqüencial, continuaria sendo executado no host com processadores genéricos, enquanto que a parte com os grandes laços de processamento seriam processados, com maior desempenho por explorar o paralelismo, nos co-processadores com FPGAs. Porém, a movimentação dos dados entre a memória principal do host e a memória externa do FPGA é considerada um grande gargalo para o processamento em hardware. Vários autores em seus trabalhos demonstram o desempenho alcançado com o uso de processamento em hardware, mas consideram que os dados já estão na memória externa do FPGA. Poucos comentam sobre a perda de desempenho quando se considera a movimentação de dados. Neste trabalho foram estudadas técnicas de particionamento de grandes matrizes densas, reuso de dados e as estratégias que melhor se adéquam para algumas arquiteturas estudadas neste trabalho. As latências desta movimentação de dados entre o host e o co-processador em FPGA foram o foco deste trabalho também. Concluímos com um estudo de caso onde propomos uma estratégia para particionamento e multiplicação de matrizes por blocos no FPGA virtex 5 (XC5VLX50T -1 FF1136), montado em uma placa (ML 555 Board) da Xilinx

Pulse subsidies account for a substantial proportion of resource availability in many systems, having persistent and cascading effects on consumer population dynamics, and the routing of energy within and across ecosystem boundaries. Although the importance of resource pulses is well-established, consumer responses and the extent of resource partitioning is not well understood. I identified a pulse of marsh cyprinodontoid, invertebrate, and sunfish prey, entering an estuary, which was met by an influx of both marsh and estuarine predators. In response to the pulse, consumers showed marked diet segregation. Bass consumed significantly more cyprinodontoids, bowfin consumed significantly more invertebrates, and snook almost exclusively targeted sunfishes. The diversity of the resource pulse subsidizes multiple consumers, routing pulsed production through various trophic pathways and across ecosystem boundaries. Preserving complex trophic linkages like those of the Everglades ecotone may be important to maintaining ecosystem function and the provisioning of services, such as recreational fisheries.

The accretion of the Earth was marked by the high-pressure segregation of most of its core, accompanied by dissolution of about 10% of one or more “light” elements into the metallic phase. Various light elements have been proposed including S, Si, C and O, with each having an effect on the partitioning behaviour of the trace elements. Metallurgical data indicate that dissolution of even small amounts of light elements in liquid Fe can have profound effects on the activities of some trace components. For instance, significant partitioning of Si into the core of the growing Earth should have affected the observed Mo content of the mantle (Ono-Nakazato et al., 2007). Here, I use the epsilon model of non-ideal interactions in Fe liquids (ε. I present interaction parameters (ε, derived from 1.5GPa, 1550-1650oC metal-silicate equilibration experiments, for W, Ni, Co and Mo in liquid Fe alloyed with C, and W, Ni, Co, Mo, Cu, Mn, Ag, Sb, Cd, In, Tl, Pb, Ga, Ge, Cr, V and Zn in liquid Fe alloyed with S. Additional epsilon values were taken from the steelmaking sourcebook when necessary. I used this new data in conjunction with published metal–silicate partitioning results to develop a model of continuous accretion and core segregation taking explicit account of the partitioning of Si (this study) and O (from Ozawa et al., 2008) between metal and silicate and their effects on metal–silicate partitioning of siderophile elements. The best model for explaining the Earth’s formation including the Mo:W ratio of the silicate Earth posits that the Earth’s oxidation state increased in steps from 1 to 6.26% FeO, increasing Si in the Earth’s core and the light elements C and S being added to the planet in the last ~20% of accretion material.

Interactions of engineered nanomaterials (ENMs) with environmental interfaces have become a critical aspect of environmental health and safety evaluations. Carbon fullerene (C₆₀) has emerged at the forefront of nanoscale research and applications due to its unique properties. Although there are concerns associated with the harmful effects of fullerene towards living organisms, the mechanisms of fullerene toxicity are still under debate. A first step toward assessing these mechanisms requires evaluation of the bio-accumulation and bio-uptake of fullerene through lipid membranes which serve as biological barriers in cells. In this dissertation, partitioning of fullerene between water and lipid membranes and cellular uptake of fullerene were investigated to assess bioavailability of this nanoparticle. Traditional methods to estimate the equilibrium partitioning of molecular level chemicals between water and lipid membranes (K[subscript lipw]) cannot be applied to measure K[subscript lipw] of nanoparticles due to the large size of nanoparticle aggregates. In this study, we developed an in vitro method to estimate K[subscript lipw] of fullerene using solid supported lipid membranes (SSLMs) with various membrane compositions. K[subscript lipw] of fullerene increased with increasing acyl chain length and K[subscript lipw] values were higher after creating phase separation in ternary lipid membranes compared to pre-phase separation. In addition, the partitioning values (K[subscript lipw]) were found to depend on the lipid head charges. These results suggest that the lipid membrane composition can be a critical factor for assessing bioaccumulation of fullerene. Evaluation of the partitioning thermodynamics of fullerene demonstrated that the partitioning mechanism of fullerene is different from that of molecular level chemicals. It is generally acknowledged that molecular level chemicals partition into the hydrophobic center of lipid membranes (i.e., absorption), however, the partitioning mechanism of fullerene is a combination of adsorption on the lipid membrane surface and absorption. Caco-2 cellular uptake of fullerene nanoparticles was investigated using an in vitro method developed in this study to distinguish between active and passive transport across cell membranes. Energy dependent endocytosis is hypothesized to be the main cellular transport mechanism based on an observed temperature dependence of cellular uptake and evidence for saturation of the active sites of transport during cellular uptake of fullerene. Metabolic inhibitors decreased the mass of fullerene taken up by the cells, which supports an active transport mechanism of fullerene through the cell membranes. To evaluate bioavilability of fullerene under environmentally relevant conditions, the effects of humic acid and fetal bovine serum (FBS) on the lipid accumulation and cellular uptake were also investigated. Humic acid and FBS changed the surface characteristics of fullerene. The presence of FBS significantly decreased lipid accumulation of fullerene presumably due to higher steric hinderance of FBS coated fullerene as well as the changes in surface energy, water solubility, and lipid solubility of charged FBS coated fullerene relative to that of bare fullerene. Both humic acid and FBS also effectively lowered the cellular uptake of fullerene. These results imply that natural organic matter and biomolecules in natural aquatic and biological environments have significant effects on the bioavilability of fullerene nanoparticles / text

Climate variability and landscape characteristics interact to define specific catchment hydrological response. Catchments are considered fundamental landscape units to study the water cycle, since all aspects of the land surface component of the hydrological cycle come together in a defined area, which enables scientific research through mass, momentum and energy budgets. The role of climate-landscape interactions in defining hydrologic partitioning, particularly at the catchment scale, however, is still poorly understood. In this study, a catchment scale process-based hydrologic model (hillslope storage Boussinesq- soil moisture model, hsB-SM) was developed to investigate such interactions. The model was applied to 12 catchments across a climate gradient. Dominant time scales (T.S.) of catchment response and their dimensionless ratios were analyzed with respect to climate and landscape features to identify similarities in catchment response. A limited number of model parameters could be related to observable landscape features. Several T.S. and dimensionless numbers show scaling relationships with respect to the investigated hydrological signatures (runoff coefficient, baseflow index, and slope of the flow duration curve). Some dimensionless numbers vary systematically across the climate gradient, pointing to the possibility that this might be the result of systematic co-variation of climate, vegetation and soil related T.S. Each of 12 behavioral hsB-SM models were subsequently subjected to each of 12 different climate forcings. Mean deviations from Budyko's hypothesis controlling long-term hydrologic partitioning (represented by the evaporation index, E/P, dependence on the aridity index, PET/P) were computed per catchment and per climate. The trend observed per catchment could be explained by the dimensionless ratio of perched aquifer storage-release T.S. and mean storm duration T.S. The trend observed per climate could be explained by an empirical relationship between fraction of rainy days and average daily temperature during those days. Catchments that produce more E/P have developed in climates that produce less E/P, when compared to Budyko's hypothesis. Also, climates that give rise to more E/P are associated with catchments that have vegetation with less efficient water use parameters. These results suggest the possibility of vegetation and soil co-evolution in response to local climate leading to (catchment scale) predictable hydrologic partitioning.

No description available.

Stability is a major requirement to draw reliable conclusions when interpreting results from supervised statistical learning. In this paper, we present a general framework for assessing and comparing the stability of results, that can be used in real-world statistical learning applications or in benchmark studies. We use the framework to show that stability is a property of both the algorithm and the data-generating process. In particular, we demonstrate that unstable algorithms (such as recursive partitioning) can produce stable results when the functional form of the relationship between the predictors and the response matches the algorithm. Typical uses of the framework in practice would be to compare the stability of results generated by different candidate algorithms for a data set at hand or to assess the stability of algorithms in a benchmark study. Code to perform the stability analyses is provided in the form of an R-package. / Series: Research Report Series / Department of Statistics and Mathematics