Efficient Algorithms for Computing All Low s-t Edge Connectivities and Related Problems

Given an undirected unweighted graph G = (V, E) and an integer k ≥ 1, we consider the problem of computing the edge connectivities of all those (s, t) vertex pairs, whose edge connectivity is at most k. We present an algorithm with expected running time Õ(m + nk3) for this problem, where |V| = n and |E| = m. Our output is a weighted tree T whose nodes are the sets V1, V2,..., V l of a partition of V, with the property that the edge connectivity in G between any two vertices s ε Vi and t ε Vj, for i ≠ j, is equal to the weight of the lightest edge on the path between Vi and Vj in T. Also, two vertices s and t belong to the same Vi for any i if and only if they have an edge connectivity greater than k. Currently, the best algorithm for this problem needs to compute all-pairs min-cuts in an O(nk) edge graph; this takes Õ(m + n5/2kmin{k1/2, n1/6}) time. Our algorithm is much faster for small values of k; in fact, it is faster whenever k is o(n5/6). Our algorithm yields the useful corollary that in Õ(m + nc3) time, where c is the size of the global min-cut, we can compute the edge connectivities of all those pairs of vertices whose edge connectivity is at most αc for some constant α. We also present an Õ(m + n) Monte Carlo algorithm for the approximate version of this problem. This algorithm is applicable to weighted graphs as well. Our algorithm, with some modifications, also solves another problem called the minimum T-cut problem. Given T ⊆ V of even cardinality, we present an Õ(m + nk3) algorithm to compute a minimum cut that splits T into two odd cardinality components, where k is the size of this cut.

Faster algorithms for all-pairs small stretch distances in weighted graphs

Abstract. Let G = (V,E) be a weighted undirected graph, with non-negative edge weights. We consider the problem of efficiently computing approximate distances between all pairs of vertices in G. While many efficient algorithms are known for this problem in unweighted graphs, not many results are known for this problem in weighted graphs. Zwick [14] showed that for any fixed ε> 0, stretch 1 1 + ε distances between all pairs of vertices in a weighted directed graph on n vertices can be computed in Õ(n ω) time, where ω < 2.376 is the exponent of matrix multiplication and n is the number of vertices. It is known that finding distances of stretch less than 2 between all pairs of vertices in G is at least as hard as Boolean matrix multiplication of two n×n matrices. It is also known that all-pairs stretch 3 distances can be computed in Õ(n 2) time and all-pairs stretch 7/3 distances can be computed in Õ(n 7/3) time. Here we consider efficient algorithms for the problem of computing all-pairs stretch (2+ε) distances in G, for any 0 < ε < 1. We show that all pairs stretch (2 + ε) distances for any fixed ε> 0 in G can be computed in expected time O(n 9/4 logn). This algorithm uses a fast rectangular matrix multiplication subroutine. We also present a combinatorial algorithm (that is, it does not use fast matrix multiplication) with expected running time O(n 9/4) for computing all-pairs stretch 5/2 distances in G. 1

Bacterial transformation using micro-shock waves

Shock waves are one of the most competent mechanisms of energy dissipation observed in nature. We have developed a novel device to generate controlled micro-shock waves using an explosive-coated polymer tube. In this study, we harnessed these controlled micro-shock waves to develop a unique bacterial transformation method. The conditions were optimized for the maximum transformation efficiency in Escherichia coli. The maximum transformation efficiency was obtained when we used a 30 cm length polymer tube, 100 mu m thick metal foil, 200 mM CaCl(2), 1 ng/mu l plasmid DNA concentration, and 1 x 10(9) cell density. The highest transformation efficiency achieved (1 x 10(-5) transformants/cell) was at least 10 times greater than the previously reported ultrasound-mediated transformation (1 x 10(-6) transformants/cell). This method was also successfully employed for the efficient and reproducible transformation of Pseudomonas aeruginosa and Salmonella typhimurium. This novel method of transformation was shown to be as efficient as electroporation with the added advantage of better recovery of cells, reduced cost (40 times cheaper than a commercial electroporator), and growth phase independent transformation. (C) 2011 Elsevier Inc. All rights reserved.

Brillouin Scattering Investigation of Solvation Dynamics in Succinonitrile-Lithium Salt Plastic Crystalline Electrolytes

Temperature dependent Brillouin scattering studies have been performed to ascertain the influence of solvent dynamics on ion-transport in succinonitrile-lithium salt plastic crystalline electrolytes. Though very rarely employed, we observe that Brillouin spectroscopy is an invaluable tool for investigation of solvent dynamics. Analysis of various acoustic (long wavelength) phonon modes observed in the Brillouin scattering spectra reveal the influence of trans-gauche isomerism and as well as ion-association effects on ion transport. Although pristine SN and dilute SN-LiClO(4) samples show only the bulk longitudinal-acoustic (LA) mode, concentrated SN-LiClO(4) (similar to 0.3-1 M) electrolytes display both the bulk LA mode as well as salt induced brillouin modes at ambient temperature. The appearance of more than one brillouin mode is attributed to the scattering of light from regions with different compressibilities (''compactness''). Correspondingly, these modes show a large decrease in the full width at half-maximum (abbreviated as nu(f)) as the temperature decreases. Anomalous temperature dependent behavior of nu(f) with addition of salt could be attributed to the presence of disorder or strong coupling with a neighbor. The shape of the spectrum was evaluated using a Lorentzian and Fano line shape function depending on the nature and behavior of the Brillouin modes.

Transport and magnetic properties of Nd1-xPbxMnO3 single crystals

Transport and magnetic properties of flux-grown Nd1−xPbxMnO3 single crystals (x=0.15–0.5) are studied in the temperature range 300–77 K and 280–2 K, respectively. Magnetization measurements with a superconducting quantum interference device confirm a paramagnetic to ferromagnetic transition around 110, 121, 150, 160, and 178 K for x=0.15, 0.2, 0.3, 0.4, and 0.5, respectively. Four probe resistivity measurements at low temperatures show a monotonic increase for x=0.15 which represents a ferromagnetic insulating (FMI) phase. For Nd0.8Pb0.2MnO3 there is a slope change present in the resistivity profile at 127 K where metal to insulator transition (MI) sets in. For x=0.3 this MI transition is more prominent. However, both these samples have FMI phase at low temperature. When the concentration of lead increases (x>0.3) the sample displays a clear insulator to metal transition with a low temperature ferromagnetic metallic phase. On the basis of these measurements we have predicted the phase diagram of Nd1−xPbxMnO3. Magnetization measurements by a vibration sample magnetometer point out the appreciable differences between zero field cooled and field cooled profiles below the ferromagnetic to paramagnetic transition temperature for all x. These are indicative of magnetic frustration.

Low threshold voltage ZnO thin film transistor with a Zn0.7Mg0.3O gate dielectric for transparent electronics

A highly transparent all ZnO thin film transistor (ZnO-TFT) with a transmittance of above 80% in the visible part of the spectrum, was fabricated by direct current magnetron sputtering, with a bottom gate configuration. The ZnO-TFT with undoped ZnO channel layers deposited on 300 nm Zn0.7Mg0.3O gate dielectric layers attains an on/off ratio of 104 and mobility of 20 cm2/V s. The capacitance-voltage (C−V) characteristics of the ZnO-TFT exhibited a transition from depletion to accumulation with a small hysteresis indicating the presence of oxide traps. The trap density was also computed from the Levinson’s plot. The use of Zn0.7Mg0.3O as a dielectric layer adds additional dimension to its applications. The room temperature processing of the device depicts the possibility of the use of flexible substrates such as polymer substrates. The results provide the realization of transparent electronics for next-generation optoelectronics.

A Fluidic Drive System for Intra-Aortic Balloon Heart Assist Device

Intra-aortic balloon pumping is a counter pulsation technique for temporary circulatory assistance in cardiogenic shock and other low cardiac output conditions. Conventional systems use a balloon at the end of a catheter driven by a solenoid valve, controlled by patient's ECG or ventricular pressure signal. This results in time delay introducted by solenoid spool inertia, gas inertia, and hysteresis effects of the solenoid. Fluidics, because of their non-moving part operation and high switching speeds, minimizes the inertial effects while contributing high reliability. This communication describes a fluidic system developed for driving the balloon accepting electric control signals.

On the mechanism of plastic flow at 86°k in quenched and aged aluminum

The plastic flow of quenched aluminium at 86°K was investigated by ‘differential-stress’ creep tests in order to evaluate the rate-controlling mechanism in as-quenched and fully aged states. The experimental values of activation volume (4·3 × 10−21 cm3 for as-quenched and 5·5×l0−21cm3 for fully aged) and the total energy for thermal activation process (0·4 ev for both) are in accordance with the jog hardening and loop hardening mechanisms in quenched and fully aged states respectively.

Dislocation mechanisms for plastic flow of nickel in the temperature range 4.2 – 1200 K

The temperature ranges of thermal and athermal deformation behaviour of nickel are identified by employing the temperature-dependence of flow-stress and strain-rate cycling data. The results are used to present a unified view of dislocation mechanisms of glide encompassing the two thermally activated and the intermediate athermal regimes of plastic flow.In the low-temperature thermally activated region (<250 K) the strain rate is found to be controlled by the repulsive intersection of glide and forest dislocations, in accordance with current ideas. The athermal stress in this region can be attributed mainly to the presence of strong attractive junctions which are overcome by means of Orowan bowing, a small contribution also coming from the elastic interactions between dislocations. The values of activation area and activation energy obtained in the high-temperature region (> 750 K) negate the operation of a diffusion-controlled mechanism. Instead, the data support a thermal activation model involving unzipping of the attractive junctions. The internal (long-range) stress contribution here results solely from the elastic interactions between dislocations. This view concerning the high-temperature plastic flow is further supported by the observation that the Cottrell–Stokes law is obeyed over large strains in the range 750–1200 K.

Constructing a wire-frame from views on arbitrary view planes for objects with conic sections inclined to all view planes

A new and efficient approach to construct a 3D wire-frame of an object from its orthographic projections is described. The input projections can be two or more and can include regular and complete auxiliary views. Each view may contain linear, circular and other conic sections. The output is a 3D wire-frame that is consistent with the input views. The approach can handle auxiliary views containing curved edges. This generality derives from a new technique to construct 3D vertices from the input 2D vertices (as opposed to matching coordinates that is prevalent in current art). 3D vertices are constructed by projecting the 2D vertices in a pair of views on the common line of the two views. The construction of 3D edges also does not require the addition of silhouette and tangential vertices and subsequently splitting edges in the views. The concepts of complete edges and n-tuples are introduced to obviate this need. Entities corresponding to the 3D edge in each view are first identified and the 3D edges are then constructed from the information available with the matching 2D edges. This allows the algorithm to handle conic sections that are not parallel to any of the viewing directions. The localization of effort in constructing 3D edges is the source of efficiency of the construction algorithm as it does not process all potential 3D edges. Working of the algorithm on typical drawings is illustrated. (C) 2011 Elsevier Ltd. All rights reserved.

Modern energy access to all in rural India: An integrated implementation strategy

Expanding energy access to the rural population of India presents a critical challenge for its government. The presence of 364 million people without access to electricity and 726 million who rely on biomass for cooking indicate both the failure of past policies and programs, and the need for a radical redesign of the current system. We propose an integrated implementation framework with recommendations for adopting business principles with innovative institutional, regulatory, financing and delivery mechanisms. The framework entails establishment of rural energy access authorities and energy access funds, both at the national and regional levels, to be empowered with enabling regulatory policies, capital resources and the support of multi-stakeholder partnership. These institutions are expected to design, lead, manage and monitor the rural energy interventions. At the other end, trained entrepreneurs would be expected to establish bioenergy-based micro-enterprises that will produce and distribute energy carriers to rural households at an affordable cost. The ESCOs will function as intermediaries between these enterprises and the international carbon market both in aggregating carbon credits and in trading them under CDM. If implemented, such a program could address the challenges of rural energy empowerment by creating access to modern energy carriers and climate change mitigation. (C) 2011 Elsevier Ltd. All rights reserved.