Finding minimum height elimination trees for interval graphs in polynomial time

The elimination tree plays an important role in many aspects of sparse matrix factorization. The height of the elimination tree presents a rough, but usually effective, measure of the time needed to perform parallel elimination. Finding orderings that produce low elimination is therefore important. As the problem of finding minimum height elimination tree orderings is NP-hard, it is interesting to concentrate on limited classes of graphs and find minimum height elimination trees for these efficiently. In this paper, we use clique trees to find an efficient algorithm for interval graphs which make an important subclass of chordal graphs. We first illustrate this method through an algorithm that finds minimum height elimination for chordal graphs. This algorithm, although of exponential time complexity, is conceptionally simple and leads to a polynomial-time algorithm for finding minimum height elimination trees for interval graphs.This work was supported by grants from the Norwegian Research Council.     

The determination of nitrate and chloride in sodium hydroxide solutions by means of cation exchangers,in the manufacturing control of alkaline batteries

The most important types of alkaline batteries are described. A method for the determination of chloride and nitrate ions in sodium hydroxide solutions has been developed The analysis is performed in the following manner: the solution is passed through a layer of a cation exchanger in the hydrogenform,wherebythe sodium hydroxide is neutralized. The liberated hydrochloric and nitric acids respectively are determined through titration. This method has been used for the manufacturing control of nickel-cadmium batteries.     

Monitoring the DNA binding kinetics of a binuclear ruthenium complex by energy transfer: evidence for slow shuffling

The semirigid binuclear ruthenium complex Delta,Delta-[mu-(11,11'-bidppz)(phen)(4)Ru(2)](4+) has been shown to rearrange slowly from an initial groove-bound nonluminescent state to a final intercalated emissive state by threading one of its bulky Ru(phen)(2) moieties through the DNA base stack. When this complex binds to poly[d(A-T)(2)], a further increase in emission from the complex is observed after completion of the intercalation, assigned to reorganization of the intercalated complex. We here report a study of the threading process in poly[d(A-T)(2)], in which the minor groove binding dye DAPI is used as an energy transfer probe molecule to assess the distribution of ruthenium complex during and also after the actual threading phase. The emission from DAPI is found to change with the same rate as the emission from the ruthenium complex, and furthermore, DAPI does not disturb the binding kinetics of the latter, justifying it as a good probe of both the threading and the reorganization processes. We conclude from the change in the emission from both DAPI and the ruthenium complex with time that DAPI-ruthenium interactions are most pronounced during the process of threading of the complex, suggesting that the complexes are initially threaded slightly anticooperatively and thereafter redistribute along the DNA to reach their thermodynamically most favorable distribution. The final distribution is characterized by a small but significant binding cooperativity, probably as a result of hydrophobic interactions between the complex ions despite their tetravalent positive charges. The mechanism of "shuffling" the complex along the DNA chain is discussed, i.e., whether the ruthenium complex remains threaded (requiring sequential base-pair openings) or if unthreading followed by lateral diffusion within the ionic atmosphere of the DNA and rethreading occurs.     

In situ reactivity and FTIR study of the wet and dry photooxidation of propane on anatase TiO2

The photocatalytic oxidation (PCO) of trace amounts of propane (500 ppm) on nanocrystalline anatase TiO2 has been investigated in situ as a function of temperature (T = 318-473 K), humidity (C(H2O) = 0-4%), and time by means of mass spectrometry and diffuse reflectance Fourier transform infrared spectroscopy (DRIFT). Propane adsorbs associatively on TiO2 at 318 K in dry air, while at 473 K small amounts of thermal dissociation products appear on the surface. In agreement with previous studies, propane is found primarily to be converted to acetone by reactions with photogenerated oxygen radicals. Various successive reaction paths exist, where the branching depends on the temperature and hydroxylation state of the surface. Under dry conditions at 318 K, acetone oxidation is initially kinetically hindered, while, above 400 K, acetone readily decomposes. The thermally assisted reaction channel leads to detrimental bonding of surface species and inhibition of the catalytic activity. It is manifested by a coloration of the sample and suggested to be coupled to surface reduction. Under humidified conditions, there is an optimum of the PCO in C(H2O) and T space, which is estimated to correspond to an equilibrium coverage of one monolayer of H2O (or bilayer). The latter reaction condition also corresponds to sustained high propane conversion and is characterized by rapid establishment of steady state rates. The optimum PCO is discussed in terms of a balance between (i) sustaining enough of a photoactive water monolayer to avoid detrimental bonding of surface species, (ii) allowing reactants to adsorb and access bulk TiO2 photoexcitations, and at the same time (iii) maximizing the thermally assisted decomposition of intermediates.     

Imaging of peptide adsorption to microfluidic channels in a plastic compact disc using a positron emitting radionuclide

A method for studying peptide-surface interactions within microfluidic channels by radionuclide imaging is described. With the high surface area-to-volume ratio of channels in miniaturised devices, combined with low amounts of analyte, non-specific peptide adsorption is a critical issue. The objective of the study was therefore to develop a method capable of direct detection of adsorbed peptide within microfluidic channels. A micro-device consisting of channels moulded in a plastic compact disc was chosen for the study, together with two selected peptides of different lengths and isoelectric point (pI) values. A bifunctional chelator, DOTA, was attached to the peptide by conjugation and labelled with the short-lived positron emitting radionuclide 68Ga. Quantitative images of radiotracer distribution within the microfluidic channels were obtained using a PhosphorImager system. The power of the method was demonstrated by the ability to clearly measure changes in adsorption when varying a number of parameters that typically affect peptide adsorption. These included surface modifications, analyte concentration, pH, and ionic strength. Additionally, two quantification methods were developed and compared. Radionuclide imaging also permitted visualisation of adsorption and release processes in microchannel chromatographic columns. The results suggest that radionuclide imaging is a suitable tool not only for the study of peptide adsorption to the microchannels presented in this study but also as a versatile tool to measure peptide-surface interactions in a wide variety of miniaturised structures and devices.     

Absorption anisotropy of cubic or randomly oriented chromophores in anisotropic solvents. Dispersion induced linear dichroism (DILD)

A new mechanism through which cubic or orientationally averaged solutes could gain absorption anisotropy (linear dichroism) in the presence of an anisotropic (oriented) solvent medium is proposed. Transitions of the unoriented species exhibit a dispersion induced linear dichroism (DILD) as a result of dispersive coupling to the transitions of the oriented system. The phenomenon depends on the nature of the angular distribution of solute molecules about a particular solvent species, being maximised for a cylindrical distribution around a polymer, but still yielding a measurable DILD for spherical distributions of the solute. It is also shown that the LD of non-cubic or oriented solutes in anisotropic media should be corrected for a significant DILD contribution.