On the Cubicity of AT-Free Graphs and Circular-Arc Graphs

A unit cube in k dimensions (k-cube) is defined as the Cartesian product R-1 x R-2 x ... x R-k where R-i (for 1 <= i <= k) is a closed interval of the form [a(i), a(i) + 1] on the real line. A graph G on n nodes is said to be representable as the intersection of k-cubes (cube representation in k dimensions) if each vertex of C can be mapped to a k-cube such that two vertices are adjacent in G if and only if their corresponding k-cubes have a non-empty intersection. The cubicity of G denoted as cub(G) is the minimum k for which G can be represented as the intersection of k-cubes. An interesting aspect about cubicity is that many problems known to be NP-complete for general graphs have polynomial time deterministic algorithms or have good approximation ratios in graphs of low cubicity. In most of these algorithms, computing a low dimensional cube representation of the given graph is usually the first step. We give an O(bw . n) algorithm to compute the cube representation of a general graph G in bw + 1 dimensions given a bandwidth ordering of the vertices of G, where bw is the bandwidth of G. As a consequence, we get O(Delta) upper bounds on the cubicity of many well-known graph classes such as AT-free graphs, circular-arc graphs and cocomparability graphs which have O(Delta) bandwidth. Thus we have: 1. cub(G) <= 3 Delta - 1, if G is an AT-free graph. 2. cub(G) <= 2 Delta + 1, if G is a circular-arc graph. 3. cub(G) <= 2 Delta, if G is a cocomparability graph. Also for these graph classes, there axe constant factor approximation algorithms for bandwidth computation that generate orderings of vertices with O(Delta) width. We can thus generate the cube representation of such graphs in O(Delta) dimensions in polynomial time.

Design of multiunit electronic exchanges through decomposition

In this paper, we exploit the idea of decomposition to match buyers and sellers in an electronic exchange for trading large volumes of homogeneous goods, where the buyers and sellers specify marginal-decreasing piecewise constant price curves to capture volume discounts. Such exchanges are relevant for automated trading in many e-business applications. The problem of determining winners and Vickrey prices in such exchanges is known to have a worst-case complexity equal to that of as many as (1 + m + n) NP-hard problems, where m is the number of buyers and n is the number of sellers. Our method proposes the overall exchange problem to be solved as two separate and simpler problems: 1) forward auction and 2) reverse auction, which turns out to be generalized knapsack problems. In the proposed approach, we first determine the quantity of units to be traded between the sellers and the buyers using fast heuristics developed by us. Next, we solve a forward auction and a reverse auction using fully polynomial time approximation schemes available in the literature. The proposed approach has worst-case polynomial time complexity. and our experimentation shows that the approach produces good quality solutions to the problem. Note to Practitioners- In recent times, electronic marketplaces have provided an efficient way for businesses and consumers to trade goods and services. The use of innovative mechanisms and algorithms has made it possible to improve the efficiency of electronic marketplaces by enabling optimization of revenues for the marketplace and of utilities for the buyers and sellers. In this paper, we look at single-item, multiunit electronic exchanges. These are electronic marketplaces where buyers submit bids and sellers ask for multiple units of a single item. We allow buyers and sellers to specify volume discounts using suitable functions. Such exchanges are relevant for high-volume business-to-business trading of standard products, such as silicon wafers, very large-scale integrated chips, desktops, telecommunications equipment, commoditized goods, etc. The problem of determining winners and prices in such exchanges is known to involve solving many NP-hard problems. Our paper exploits the familiar idea of decomposition, uses certain algorithms from the literature, and develops two fast heuristics to solve the problem in a near optimal way in worst-case polynomial time.

Iron(III) Schiff base complexes of arginine and lysine as netropsin mimics showing AT-selective DNA binding and photonuclease activity

Iron(III) complexes [Fe(L)(2)]Cl (1-3), where L is monoanionic N-salicylidene-arginine (sal-argH for 1), hydroxynaphthylidene-arginine (nap-argH for 2) and N-salicylidene-lysine (sal-lysH for 3), were prepared and their DNA binding and photo-induced DNA cleavage activity studied. Complex 3 as its hexafluorophosphate salt [Fe(sal-lysH)(2)](PF6)center dot 6H(2)O (3a) was structurally characterized by single crystal Xray crystallography. The crystals belonged to the triclinic space group P-1. The complex has two tridentate ligands in FeN2O4 coordination geometry with two pendant cationic amine moieties. Complexes 1 and 2 with two pendant cationic guanidinium moieties are the structural models for the antitumor antibiotics netropsin. The complexes are stable and soluble in water. They showed quasi-reversible Fe(III)/Fe(II) redox couple near 0.6 V in H2O-0.1 M KCl. The high-spin 3d(5)-iron(III) complexes with mu(eff) value of similar to 5.9 mu(B) displayed ligand-to-metal charge transfer electronic band near 500 mm in Tris-HCl buffer. The complexes show binding to Calf Thymus (CT) DNA. Complex 2 showed better binding propensity to the synthetic oligomer poly(dA)center dot poly(dT) than to CT-DNA or poly(dG)center dot poly(dC). All the complexes displayed chemical nuclease activity in the presence of 3-mercaptopropionic acid as a reducing agent and cleaved supercoiled pUC19 DNA to its nicked circular form. They exhibited photo-induced DNA cleavage activity in UV-A light and visible light via a mechanistic pathway that involves the formation of reactive hydroxyl radical species. (C) 2010 Elsevier Inc. All rights reserved.

The third post-Newtonian gravitational wave polarizations and associated spherical harmonic modes for inspiralling compact binaries in quasi-circular orbits

The gravitational waveform (GWF) generated by inspiralling compact binaries moving in quasi-circular orbits is computed at the third post-Newtonian (3PN) approximation to general relativity. Our motivation is two-fold: (i) to provide accurate templates for the data analysis of gravitational wave inspiral signals in laser interferometric detectors; (ii) to provide the associated spin-weighted spherical harmonic decomposition to facilitate comparison and match of the high post-Newtonian prediction for the inspiral waveform to the numerically-generated waveforms for the merger and ringdown. This extension of the GWF by half a PN order (with respect to previous work at 2.5PN order) is based on the algorithm of the multipolar post-Minkowskian formalism, and mandates the computation of the relations between the radiative, canonical and source multipole moments for general sources at 3PN order. We also obtain the 3PN extension of the source multipole moments in the case of compact binaries, and compute the contributions of hereditary terms (tails, tails-of-tails and memory integrals) up to 3PN order. The end results are given for both the complete plus and cross polarizations and the separate spin-weighted spherical harmonic modes.

The use of circular surface aerators in wastewater treatment tanks

Aeration experiments were conducted in different sized baffled and unbaffled circular surface aeration tanks to study their relative performance on oxygen transfer process while aerating the same volume of water. Experiments were carried out with the objective of ascertaining the effect of baffle on oxygen transfer coefficient k. Simulation equations govern the oxygen transfer coefficient with the theoretical power per unit volume, X and actual power per unit volume, P-V. It has been found that, for any given X, circular tanks with baffle produce higher values of k than unbaffled circular tanks, but in terms of actual power consumption unbaffled tanks consume less power when compared to baffled circular tanks to achieve the same value of k. It has been found that in terms of energy consumption, epsilon, baffled tanks consume more energy than unbaffled tanks at any value of X. This suggests that the unbaffled circular tank gives a better performance as far as energy consumption is concerned and hence better economy. An example illustrating the energy conservation to aerate the same volume of water in both types of aerators is given. (c) 2007 Society of Chemical Industry.

Stability of an unsupported vertical circular excavation in clays under undrained condition

By using the axisymmetric finite elements static limit analysis formulation, proposed recently by the authors, the stability numbers (gamma H/c(o)) for an unsupported vertical circular excavation in clays, whose cohesion increases with depth, have been determined under undrained condition; gamma = unit weight, H., height of the excavation and c(o) = cohesion along ground surface. The results are obtained for various values of H/b and m; where b = the radius of the excavation and m = a non-dimensional parameter which accounts for the rate of the increase of cohesion with depth. The values of the stability numbers increase continuously both with increases in H/b and m. The results obtained in this study compare well with those available in literature.(C) 2009 Elsevier Ltd. All rights reserved.

Electronic excitations in solids studied using inelastic x-ray scattering

Inelastic x-ray scattering can be used to study the electronic structure of matter. The x rays scattered from the target both induce and carry information on the electronic excitations taking place in the system. These excitations are the manifestations of the electronic structure and the physics governing the many-body system. This work presents results of non-resonant inelastic x-ray scattering experiments on a range of materials including metallic, insulating and semiconducting compounds as well as an organic polymer. The experiments were carried out at the National Synchrotron Light Source, USA and at the European Synchrotron Radiation Facility, France. The momentum transfer dependence of the experimental valence- and core-electron excitation spectra is compared with the results of theoretical first principles computations that incorporate the electron-hole interaction. A recently developed method for analyzing the momentum transfer dependence of core-electron excitation spectra is studied in detail. This method is based on real space multiple scattering calculations and is used to extract the angular symmetry components of the local unoccupied density of final states.

Studies of electronic structure by x-ray Raman and emission spectroscopy: applications to MgB2 superconductors and high pressure physics

X-ray Raman scattering and x-ray emission spectroscopies were used to study the electronic properties and phase transitions in several condensed matter systems. The experimental work, carried out at the European Synchrotron Radiation Facility, was complemented by theoretical calculations of the x-ray spectra and of the electronic structure. The electronic structure of MgB2 at the Fermi level is dominated by the boron σ and π bands. The high density of states provided by these bands is the key feature of the electronic structure contributing to the high critical temperature of superconductivity in MgB2. The electronic structure of MgB2 can be modified by atomic substitutions, which introduce extra electrons or holes into the bands. X ray Raman scattering was used to probe the interesting σ and π band hole states in pure and aluminum substituted MgB2. A method for determining the final state density of electron states from experimental x-ray Raman scattering spectra was examined and applied to the experimental data on both pure MgB2 and on Mg(0.83)Al(0.17)B2. The extracted final state density of electron states for the pure and aluminum substituted samples revealed clear substitution induced changes in the σ and π bands. The experimental work was supported by theoretical calculations of the electronic structure and x-ray Raman spectra. X-ray emission at the metal Kβ line was applied to the studies of pressure and temperature induced spin state transitions in transition metal oxides. The experimental studies were complemented by cluster multiplet calculations of the electronic structure and emission spectra. In LaCoO3 evidence for the appearance of an intermediate spin state was found and the presence of a pressure induced spin transition was confirmed. Pressure induced changes in the electronic structure of transition metal monoxides were studied experimentally and were analyzed using the cluster multiplet approach. The effects of hybridization, bandwidth and crystal field splitting in stabilizing the high pressure spin state were discussed. Emission spectroscopy at the Kβ line was also applied to FeCO3 and a pressure induced iron spin state transition was discovered.

Nickel(II) meso-hydroxyporphyrin complexes revisited: Palladium-catalysed synthesis, electronic structures of derived oxy radicals, and oxidative coupling to a dioxoporphodimethene dyad

We report the synthesis and characterisation of new examples of meso-hydroxynickel(II) porphyrins with 5,15-diphenyl and 10-phenyl-5,15-diphenyl/diaryl substitu- tion. The OH group was introduced by using carbonate or hydroxide as nucleophile by using palladium/phosphine cat- alysis. The NiPor OHs exist in solution in equilibrium with the corresponding oxy radicals NiPor OC. The 15-phenyl group stabilises the radicals, so that the 1H NMR spectra of {NiPor OH} are extremely broad due to chemical exchange with the paramagnetic species. The radical concentration for the diphenylporphyrin analogue is only 1%, and its NMR line-broadening was able to be studied by variable-tempera- ture NMR spectroscopy. The EPR signals of NiPor OC are con- sistent with somewhat delocalised porphyrinyloxy radicals, and the spin distributions calculated by using density func- tional theory match the EPR and NMR spectroscopic obser- vations. Nickel(II) meso-hydroxy-10,20-diphenylporphyrin was oxidatively coupled to a dioxo-terminated porphodimethene dyad, the strongly red-shifted electronic spectrum of which was successfully modelled by using time-dependent DFT calculations.

Electronic structure and bonding of beta-rhombohedral boron using cluster fragment approach

Theoretical studies using density functional theory are carried out to understand the electronic structure and bonding and electronic properties of elemental beta-rhombohedral boron. The calculated band structure of ideal beta-rhombohedral boron (B-105) shows valence electron deficiency and depicts metallic behavior. This is in contrast to the experimental result that it is a semiconductor. To understand this ambiguity we discuss the electronic structure and bonding of this allotrope with cluster fragment approach using our recently proposed mno rule. This helps us to comprehend in greater detail the structure of B-105 and materials which are closely related to beta-rhombohedral boron. The molecular structures B12H12-2, B28H21+1, BeB27H21, LiB27H21-1, CB27H21+2, B57H36+3, Be3B54H36, and Li2CB54H36, and corresponding solids Li8Be3B102 and Li10CB102 are arrived at using these ideas and studied using first principles density functional theory calculations.

Flow driven electronic transport in carbon nan otubes

The flow of a liquid on single-walled carbon nanotube bundles induces an electrical signal (voltage/current) in the sample along the direction of the flow. The electrical response is found to be logarithmic in the flow speed over a wide range. The magnitude of the flow induced electrical signal generated depends sensitively on the ionic conductivity and the polar nature of the liquid, and electrical biasing of the nanotubes can control its direction. Our measurements suggest that the dominant mechanism responsible for this highly sub-linear response should involve a direct forcing of the free charge carriers in the nanotubes by the fluctuating Coulombic field of the liquid flowing past it.

Ring loading of a long, thin, circular cylindrical shell enclosing a soft, solid core: A recalculation by the love function method of elasticity.

The problem is solved using the Love function and Flügge shell theory. Numerical work has been done with a computer for various values of shell geometry parameters and elastic constants.