A Linear Time Algorithm for Computing Longest Paths in Cactus Graphs

ACM Computing Classification System (1998): G.2.2.

An adaptive hierarchical approach to the extraction of high resolution medial surfaces

We introduce a novel algorithm for medial surfaces extraction that is based on the density-corrected Hamiltonian analysis. The approach extracts the skeleton directly from a triangulated mesh and adopts an adaptive octree-based approach in which only skeletal voxels are refined to a lower level of the hierarchy, resulting in robust and accurate skeletons at extremely high resolution. The quality of the extracted medial surfaces is confirmed by an extensive set of experiments. © 2012 IEEE.

Programming and Testing a Two-Tree Algorithm

ACM Computing Classification System (1998): G.2.2, F.2.2.

Model Mining and Efficient Verification of Software Product Lines

Software product line modeling aims at capturing a set of software products in an economic yet meaningful way. We introduce a class of variability models that capture the sharing between the software artifacts forming the products of a software product line (SPL) in a hierarchical fashion, in terms of commonalities and orthogonalities. Such models are useful when analyzing and verifying all products of an SPL, since they provide a scheme for divide-and-conquer-style decomposition of the analysis or verification problem at hand. We define an abstract class of SPLs for which variability models can be constructed that are optimal w.r.t. the chosen representation of sharing. We show how the constructed models can be fed into a previously developed algorithmic technique for compositional verification of control-flow temporal safety properties, so that the properties to be verified are iteratively decomposed into simpler ones over orthogonal parts of the SPL, and are not re-verified over the shared parts. We provide tool support for our technique, and evaluate our tool on a small but realistic SPL of cash desks.

Efficient algorithm for routing optimization via statistical mechanics

Many practical routing algorithms are heuristic, adhoc and centralized, rendering generic and optimal path configurations difficult to obtain. Here we study a scenario whereby selected nodes in a given network communicate with fixed routers and employ statistical physics methods to obtain optimal routing solutions subject to a generic cost. A distributive message-passing algorithm capable of optimizing the path configuration in real instances is devised, based on the analytical derivation, and is greatly simplified by expanding the cost function around the optimized flow. Good algorithmic convergence is observed in most of the parameter regimes. By applying the algorithm, we study and compare the pros and cons of balanced traffic configurations to that of consolidated traffic, which provides important implications to practical communication and transportation networks. Interesting macroscopic phenomena are observed from the optimized states as an interplay between the communication density and the cost functions used. © 2013 IEEE.

Partial Ovoids and Partial Spreads of Classical Finite Polar Spaces

2000 Mathematics Subject Classification: 05B25, 51E20.

Efficient computation of decoherent quantum walks through eigenvalue perturbation

A number of recent studies have investigated the introduction of decoherence in quantum walks and the resulting transition to classical random walks. Interestingly,it has been shown that algorithmic properties of quantum walks with decoherence such as the spreading rate are sometimes better than their purely quantum counterparts. Not only quantum walks with decoherence provide a generalization of quantum walks that naturally encompasses both the quantum and classical case, but they also give rise to new and different probability distribution. The application of quantum walks with decoherence to large graphs is limited by the necessity of evolving state vector whose sizes quadratic in the number of nodes of the graph, as opposed to the linear state vector of the purely quantum (or classical) case. In this technical report,we show how to use perturbation theory to reduce the computational complexity of evolving a continuous-time quantum walk subject to decoherence. More specifically, given a graph over n nodes, we show how to approximate the eigendecomposition of the n2×n2 Lindblad super-operator from the eigendecomposition of the n×n graph Hamiltonian.

Teaching Sorting in ICT

This article is aimed at considering how an algorithmic problem - more precisely a sorting problem - can be used in an informatics class in primary and secondary education to make students mobilize the largest possible amount of their intellectual skills in the problem solving process. We will be outlining a method which essentially forces students to utilize their mathematical knowledge besides algorithmization in order to provide an efficient solution. What is more, they are expected to use efficiently a tool that has so far not been associated with creative thinking. Sorting is meant to be just an example, through which our thoughts can easily be demonstrated, but - of course the method of education outlined can be linked to several other algorithmic problems, as well.

Occurrence and distribution of novel botryococcene hydrocarbons in freshwater wetlands of the Florida Everglades

A high abundance of isoprenoid hydrocarbons, the botryococcenes, with carbon numbers from 32 to 34 were detected in the Florida Everglades freshwater wetlands. These compounds were present in varying amounts up to 106 μg/gdw in periphyton, 278 μg/gdw in floc, and 46 μg/gdw in soils. Their structures were determined based on comparison to standards, interpretation of their mass spectra and those of their hydrogenation products, and comparison of Kovats indexes to those reported in the literature. A total of 26 cyclic and acyclic botryococcenes with 8 skeletons were identified, including those with fewer degrees of unsaturation, which are proposed as early diagenetic derivatives from the natural products. This is the first report that botryococcenes occur in the Everglades freshwater wetlands. Their potential biogenetic sources from green algae and cyanobacteria were examined, but neither contained botryococcenes. Thus, the source implication of botryococcenes in this ecosystem needs further study.

Characterization of a Novel Mouse Phenotype with Marked Hydrocephalus

In multigenic diseases, disorders where mutations in multiple genes affect the expressivity of the disease, genetic interactions play a major role in prevalence and phenotypic severity. While studying the genetic interactions between Pax3 and EdnrB in the melanocyte lineage, a new phenotype was noted in 80% of Pax3 mutants that we believe to be a novel murine model for hydrocephalus. Hydrocephalus, an accumulation of cerebrospinal fluid in the cranial cavity due to obstruction of flow in and out of the cavity, is one of the most common birth defects surpassing Down syndrome. Characteristic to hydrocephalus is a "domed" head appearance, expansion of the ventricles of the brain, and loss of neurons with hyperproliferation of glial cell types all three of which were seen in the mutant mice. The phenotype also consisted of craniofacial deformities coupled with skeletal defects including, but not limited to kyphosis, lordosis, and an apparent shortening of the some limbs. For the cellular analysis of the hydrocephalus phenotype, brains were removed and stained with two antibodies: Glial Fibrillary Acidic Protein (GFAP) and Neurofilament (NF), which are astrocyte- and neuron- specific respectively. A higher number of cells expressing GF AP and a lower number of cells expressing NF were seen in the mutant brain, when compared to control. For skeletal deformity analysis, affected mice skeletons were stained with Alizarin Red and Alcian Blue showing no apparent difference in ossification. Future genetic analysis of these mutant mice has the potential to identify novel gene modifiers involved in the promotion of this particular phenotype.

Seawater carbonate chemistry and processes during experiments with coccolithophores (Emiliania huxleyi and Gephyrocapsa oceanica), 2000

The formation of calcareous skeletons by marine planktonic organisms and their subsequent sinking to depth generates a continuous rain of calcium carbonate to the deep ocean and underlying sediments1. This is important in regulating marine carbon cycling and ocean-atmosphere CO2 exchange2. The present rise in atmospheric CO2 levels3 causes significant changes in surface ocean pH and carbonate chemistry4. Such changes have been shown to slow down calcification in corals and coralline macroalgae5,6, but the majority of marine calcification occurs in planktonic organisms. Here we report reduced calcite production at increased CO2 concentrations in monospecific cultures of two dominant marine calcifying phytoplankton species, the coccolithophorids Emiliania huxleyi and Gephyrocapsa oceanica . This was accompanied by an increased proportion of malformed coccoliths and incomplete coccospheres. Diminished calcification led to a reduction in the ratio of calcite precipitation to organic matter production. Similar results were obtained in incubations of natural plankton assemblages from the north Pacific ocean when exposed to experimentally elevated CO2 levels. We suggest that the progressive increase in atmospheric CO2 concentrations may therefore slow down the production of calcium carbonate in the surface ocean. As the process of calcification releases CO2 to the atmosphere, the response observed here could potentially act as a negative feedback on atmospheric CO2 levels.

Data compilation on the biological response to ocean acidification: environmental and experimental context of data sets and related literature

The exponential growth of studies on the biological response to ocean acidification over the last few decades has generated a large amount of data. To facilitate data comparison, a data compilation hosted at the data publisher PANGAEA was initiated in 2008 and is updated on a regular basis (doi:10.1594/PANGAEA.149999). By January 2015, a total of 581 data sets (over 4 000 000 data points) from 539 papers had been archived. Here we present the developments of this data compilation five years since its first description by Nisumaa et al. (2010). Most of study sites from which data archived are still in the Northern Hemisphere and the number of archived data from studies from the Southern Hemisphere and polar oceans are still relatively low. Data from 60 studies that investigated the response of a mix of organisms or natural communities were all added after 2010, indicating a welcomed shift from the study of individual organisms to communities and ecosystems. The initial imbalance of considerably more data archived on calcification and primary production than on other processes has improved. There is also a clear tendency towards more data archived from multifactorial studies after 2010. For easier and more effective access to ocean acidification data, the ocean acidification community is strongly encouraged to contribute to the data archiving effort, and help develop standard vocabularies describing the variables and define best practices for archiving ocean acidification data.

Seawater carbonate chemistry and skeletal development, size, weight, total lipid and symbiont density of coral Favia fragum in a laboratory experiment

Ocean acidification (OA) threatens the existence of coral reefs by slowing the rate of calcium carbonate (CaCO3) production of framework-building corals thus reducing the amount of CaCO3 the reef can produce to counteract natural dissolution. Some evidence exists to suggest that elevated levels of dissolved inorganic nutrients can reduce the impact of OA on coral calcification. Here, we investigated the potential for enhanced energetic status of juvenile corals, achieved via heterotrophic feeding, to modulate the negative impact of OA on calcification. Larvae of the common Atlantic golf ball coral, Favia fragum, were collected and reared for 3 weeks under ambient (421 µatm) or significantly elevated (1,311 µatm) CO2 conditions. The metamorphosed, zooxanthellate spat were either fed brine shrimp (i.e., received nutrition from photosynthesis plus heterotrophy) or not fed (i.e., primarily autotrophic). Regardless of CO2 condition, the skeletons of fed corals exhibited accelerated development of septal cycles and were larger than those of unfed corals. At each CO2 level, fed corals accreted more CaCO3 than unfed corals, and fed corals reared under 1,311 µatm CO2 accreted as much CaCO3 as unfed corals reared under ambient CO2. However, feeding did not alter the sensitivity of calcification to increased CO2; Delta calcification/Delta Omega was comparable for fed and unfed corals. Our results suggest that calcification rates of nutritionally replete juvenile corals will decline as OA intensifies over the course of this century. Critically, however, such corals could maintain higher rates of skeletal growth and CaCO3 production under OA than those in nutritionally limited environments.

Seawater carbonate chemistry and calcification in the tropical urchin Echinometra viridis in a laboratory experiment

Atmospheric carbon dioxide (pCO2) has risen from approximately 280 to 400 ppm since the Industrial Revolution, due mainly to the combustion of fossil fuels, deforestation, and cement production. It is predicted to reach as high as 900 ppm by the end of this century. Ocean acidification resulting from the release of anthropogenic CO2 has been shown to impair the ability of some marine calcifiers to build their shells and skeletons. Here, we present the results of ocean acidification experiments designed to assess the effects of an increase in atmospheric pCO2 from ca. 448 to 827 ppm on calcification rates of the tropical urchin Echinometra viridis. Experiments were conducted under the urchin's winter (20 °C) and summer (30 °C) water temperatures in order to identify seasonal differences in the urchin's response to ocean acidification. The experiments reveal that calcification rates decreased for urchins reared under elevated pCO2, with the decline being more pronounced under wintertime temperatures than under summertime temperatures. These results indicate that the urchin E. viridis will be negatively impacted by CO2-induced ocean acidification that is predicted to occur by the end of this century. These results also suggest that impact of CO2-induced ocean acidification on urchin calcification will be more severe in the winter and in cooler waters.

Physical properties and sedimentology of 4 profiles fom the South Atlantic

Ultrasonic P wavc transmission seismograms recorded on sediment cores have been analyzed to study the acoustic and estimate the clastic properties of marine sediments from different provinces dominated by terrigenous, calcareous, amI diatomaceous sedimentation. Instantaneous frequencies computed from the transmission seismograms are displayed as gray-shaded images to give an acoustic overview of the lithology of each core. Ccntirneter-scale variations in the ultrasonic waveforms associated with lithological changes are illustrated by wiggle traces in detail. Cross-correlation, multiple-filter, and spectral ratio techniques are applied to derive P wave velocities and attenuation coefficients. S wave velocities and attenuation coefficients, elastic moduli, and permeabilities are calculated by an inversion scheme based on the Biot-Stoll viscoelastic model. Together wilh porosity measurements, P and S wave scatter diagrams are constructed to characterize different sediment types by their velocity- and attenuation-porosity relationships. They demonstrate that terrigenous, calcareous, and diatomaceous sediments cover different velocity- and attenuation-porosity ranges. In terrigcnous sediments, P wave vclocities and attenuation coefficients decrease rapidly with increasing porosity, whereas S wave velocities and shear moduli are very low. Calcareous sediments behave similarly at relatively higher porosities. Foraminifera skeletons in compositions of terrigenous mud and calcareous ooze cause a stiffening of the frame accompanied by higher shear moduli, P wave velocities, and attenuation coefficients. In diatomaceous ooze the contribution of the shear modulus becomes increasingly important and is controlled by the opal content, whereas attenuation is very low. This leads to the opportunity to predict the opal content from nondestructive P wave velocity measurements at centimeter-scale resolution.