A combined evolutionary search and multilevel optimisation approach to graph-partitioning

The graph-partitioning problem is to divide a graph into several pieces so that the number of vertices in each piece is the same within some defined tolerance and the number of cut edges is minimised. Important applications of the problem arise, for example, in parallel processing where data sets need to be distributed across the memory of a parallel machine. Very effective heuristic algorithms have been developed for this problem which run in real-time, but it is not known how good the partitions are since the problem is, in general, NP-complete. This paper reports an evolutionary search algorithm for finding benchmark partitions. A distinctive feature is the use of a multilevel heuristic algorithm to provide an effective crossover. The technique is tested on several example graphs and it is demonstrated that our method can achieve extremely high quality partitions significantly better than those found by the state-of-the-art graph-partitioning packages.

Matching search in fractal video compression and its parallel implementation in distributed computing environments

Fractal video compression is a relatively new video compression method. Its attraction is due to the high compression ratio and the simple decompression algorithm. But its computational complexity is high and as a result parallel algorithms on high performance machines become one way out. In this study we partition the matching search, which occupies the majority of the work in a fractal video compression process, into small tasks and implement them in two distributed computing environments, one using DCOM and the other using .NET Remoting technology, based on a local area network consists of loosely coupled PCs. Experimental results show that the parallel algorithm is able to achieve a high speedup in these distributed environments.

Hierarchical random walks in trace fossils and the origin of optimal search behavior

Efficient searching is crucial for timely location of food and other resources. Recent studies show diverse living animals employ a theoretically optimal scale-free random search for sparse resources known as a Lévy walk, but little is known of the origins and evolution of foraging behaviour and the search strategies of extinct organisms. Here we show using simulations of self-avoiding trace fossil trails that randomly introduced strophotaxis (U-turns) – initiated by obstructions such as ¬¬¬self-trail avoidance or innate cueing – leads to random looping patterns with clustering across increasing scales that is consistent with the presence of Lévy walks. This predicts optimal Lévy searches can emerge from simple behaviours observed in fossil trails. We then analysed fossilized trails of benthic marine organisms using a novel path analysis technique and find the first evidence of Lévy-like search strategies in extinct animals. Our results show that simple search behaviours of extinct animals in heterogeneous environments give rise to hierarchically nested Brownian walk clusters that converge to optimal Lévy patterns. Primary productivity collapse and large-scale food scarcity characterising mass extinctions evident in the fossil record may have triggered adaptation of optimal Lévy-like searches. The findings suggest Lévy-like behaviour has been employed by foragers since at least the Eocene but may have a more ancient origin, which could explain recent widespread observations of such patterns among modern taxa.

CARBON MONOXIDE AND PREGNANCY: A SEARCH FOR A POSSIBLE THERAPEUTIC IN THE TREATMENT OF PRE-ECLAMPSIA

Pre-eclampsia (PE) is a pregnancy disorder that affects roughly 5-7% of all pregnancies and is a leading cause of both maternal and fetal/neonatal morbidity and mortality. With no present cure for the disease, researchers are interested in the lower incidence of PE observed among the cigarette smoking pregnant population. However, women who use smokeless tobacco do not experience the same decreased incidence of PE, leading to hypothesis of protection against PE from the largest combustible product of cigarette smoke, carbon monoxide (CO). Studies evaluated levels of CO in PE women and found that they were statistically lower than those of healthy pregnancy. Researchers have found CO to possess many cytoprotective and regulatory properties and specifically within the placenta, it has been found to increase perfusion pressure, decrease oxidative stress, decreases ischemia/reperfusion induced apoptosis and maintain endothelial functioning. The idea for use of CO as a possible therapeutic for PE has thus become a real possibility. This study determined CO levels in pregnant women ± smoking as well as in PE women±smoking, as to discover a possible therapeutic range for future treatments. The best correlated automated CO measurement device with blood CO levels was determined, for use in future clinical studies. This thesis also sought a possible CO delivery concentration, in order to achieve the CO levels observed in the human correlation study. A threshold level of maternal CO exposure in a murine animal model was found, for which fetal and maternal negative toxicities were not observed. The results of this thesis lend a few more pieces to the complicated puzzle involving CO and PE and offer another step toward the possibility of a therapeutic treatment/prevention using this gaseous molecule.

The Violent Maintenance of the Portuguese Colonial Identity and the Search for a Postcolonial one: literary images of Portugal as a colonial and postcolonial nation

Through the examination of Camões's Os Lusíadas , Sena's Os Grão-Capitães and Saramago's A Jangada de Pedra , this article explores violence as a means of shaping Portuguese identity in different historical contexts, and how these works portray the continued recourse to violence as Portugal moves from colonizing to postcolonial nation.