On a Special Co-cycle Basis of Graphs

In this paper we consider the problems of computing a minimum co-cycle basis and a minimum weakly fundamental co-cycle basis of a directed graph G. A co-cycle in G corresponds to a vertex partition (S,V ∖ S) and a { − 1,0,1} edge incidence vector is associated with each co-cycle. The vector space over ℚ generated by these vectors is the co-cycle space of G. Alternately, the co-cycle space is the orthogonal complement of the cycle space of G. The minimum co-cycle basis problem asks for a set of co-cycles that span the co-cycle space of G and whose sum of weights is minimum. Weakly fundamental co-cycle bases are a special class of co-cycle bases, these form a natural superclass of strictly fundamental co-cycle bases and it is known that computing a minimum weight strictly fundamental co-cycle basis is NP-hard. We show that the co-cycle basis corresponding to the cuts of a Gomory-Hu tree of the underlying undirected graph of G is a minimum co-cycle basis of G and it is also weakly fundamental.

New approximation algorithms for minimum cycle bases of graphs

We consider the problem of computing an approximate minimum cycle basis of an undirected edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. We present two new algorithms to compute an approximate minimum cycle basis. For any integer k >= 1, we give (2k - 1)-approximation algorithms with expected running time 0(kmn(1+2/k) + mn((1+1/k)(omega-1))) and deterministic running time 0(n(3+2/k)), respectively. Here omega is the best exponent of matrix multiplication. It is presently known that omega < 2.376. Both algorithms are o(m(omega)) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Theta(m(omega)) bound. We also present a 2-approximation algorithm with O(m(omega) root n log n) expected running time, a linear time 2-approximation algorithm for planar graphs and an O(n(3)) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.

RECONNECT: A NoC for polymorphic ASICs using a low overhead single cycle router

A polymorphic ASIC is a runtime reconfigurable hardware substrate comprising compute and communication elements. It is a ldquofuture proofrdquo custom hardware solution for multiple applications and their derivatives in a domain. Interoperability between application derivatives at runtime is achieved through hardware reconfiguration. In this paper we present the design of a single cycle Network on Chip (NoC) router that is responsible for effecting runtime reconfiguration of the hardware substrate. The router design is optimized to avoid FIFO buffers at the input port and loop back at output crossbar. It provides virtual channels to emulate a non-blocking network and supports a simple X-Y relative addressing scheme to limit the control overhead to 9 bits per packet. The 8times8 honeycomb NoC (RECONNECT) implemented in 130 nm UMC CMOS standard cell library operates at 500 MHz and has a bisection bandwidth of 28.5 GBps. The network is characterized for random, self-similar and application specific traffic patterns that model the execution of multimedia and DSP kernels with varying network loads and virtual channels. Our implementation with 4 virtual channels has an average network latency of 24 clock cycles and throughput of 62.5% of the network capacity for random traffic. For application specific traffic the latency is 6 clock cycles and throughput is 87% of the network capacity.

Effect of boundary condition description on convergence of solution in a boundary-value problem

It is well known that the numerical accuracy of a series solution to a boundary-value problem by the direct method depends on the technique of approximate satisfaction of the boundary conditions and on the stage of truncation of the series. On the other hand, it does not appear to be generally recognized that, when the boundary conditions can be described in alternative equivalent forms, the convergence of the solution is significantly affected by the actual form in which they are stated. The importance of the last aspect is studied for three different techniques of computing the deflections of simply supported regular polygonal plates under uniform pressure. It is also shown that it is sometimes possible to modify the technique of analysis to make the accuracy independent of the description of the boundary conditions.

Metabolism of Plasmodium berghei. I. Krebs cycle

The free parasites of Plasmodium berghei, obtained from infected cells of rats using an antiserum method, were investigated to study the operation of Krebs cycle. P. berghei was found to respire only with succinate; pyruvate, and other substrates of the Krebs cycle were not oxidized. The presence of a succinate dehydrogenase and a functioning cytochrome oxidase system was demonstrated. Cell-free extracts of free parasites showed the presence of enzymes for the utilization of C4 dicarboxylic acids; other enzymes of the Krebs cycle could not be detected. P. berghei differs from other species of Plasmodium in this respect.

Development and transient performance results of a single stage activated carbon - HFC 134a closed cycle adsorption cooling system

A laboratory model of a thermally driven adsorption refrigeration system with activated carbon as the adsorbent and 1,1,1,2-tetrafluoroethane (HFC 134a) as the refrigerant was developed. The single stage compression system has an ensemble of four adsorbers packed with Maxsorb II specimen of activated carbon that provide a near continuous flow which caters to a cooling load of up to 5W in the 5-18 degrees C region. The objective was to utilise the low grade thermal energy to drive a refrigeration system that can be used to cool some critical electronic components. The laboratory model was tested for it performance at various cooling loads with the heat source temperature from 73 to 93 degrees C. The pressure transients during heating and cooling phases were traced. The cyclic steady state and transient performance data are presented. (C) 2010 Elsevier Ltd. All rights reserved.

Fast versus slow response in climate change: implications for the global hydrological cycle

Recent studies have shown that changes in global mean precipitation are larger for solar forcing than for CO2 forcing of similar magnitude.In this paper, we use an atmospheric general circulation model to show that the differences originate from differing fast responses of the climate system. We estimate the adjusted radiative forcing and fast response using Hansen's ``fixed-SST forcing'' method.Total climate system response is calculated using mixed layer simulations using the same model. Our analysis shows that the fast response is almost 40% of the total response for few key variables like precipitation and evaporation. We further demonstrate that the hydrologic sensitivity, defined as the change in global mean precipitation per unit warming, is the same for the two forcings when the fast responses are excluded from the definition of hydrologic sensitivity, suggesting that the slow response (feedback) of the hydrological cycle is independent of the forcing mechanism. Based on our results, we recommend that the fast and slow response be compared separately in multi-model intercomparisons to discover and understand robust responses in hydrologic cycle. The significance of this study to geoengineering is discussed.

Glioblastoma-Specific Protein Interaction Network Identifies PP1A and CSK21 as Connecting Molecules between Cell Cycle-Associated Genes

Glioblastoma (GBM; grade IV astrocytoma) is a very aggressive form of brain cancer with a poor survival and few qualified predictive markers. This study integrates experimentally validated genes that showed specific upregulation in GBM along with their protein-protein interaction information. A system level analysis was used to construct GBM-specific network. Computation of topological parameters of networks showed scale-free pattern and hierarchical organization. From the large network involving 1,447 proteins, we synthesized subnetworks and annotated them with highly enriched biological processes. A careful dissection of the functional modules, important nodes, and their connections identified two novel intermediary molecules CSK21 and protein phosphatase 1 alpha (PP1A) connecting the two subnetworks CDC2-PTEN-TOP2A-CAV1-P53 and CDC2-CAV1-RB-P53-PTEN, respectively. Real-time quantitative reverse transcription-PCR analysis revealed CSK21 to be moderately upregulated and PP1A to be overexpressed by 20-fold in GBM tumor samples. Immunohistochemical staining revealed nuclear expression of PP1A only in GBM samples. Thus, CSK21 and PP1A, whose functions are intimately associated with cell cycle regulation, might play key role in gliomagenesis. Cancer Res; 70(16); 6437-47. (C)2010 AACR.

Gauge theory of a group of diffeomorphisms. III. The fiber bundle description

A new fiber bundle approach to the gauge theory of a group G that involves space‐time symmetries as well as internal symmetries is presented. The ungauged group G is regarded as the group of left translations on a fiber bundle G(G/H,H), where H is a closed subgroup and G/H is space‐time. The Yang–Mills potential is the pullback of the Maurer–Cartan form and the Yang–Mills fields are zero. More general diffeomorphisms on the bundle space are then identified as the appropriate gauged generalizations of the left translations, and the Yang–Mills potential is identified as the pullback of the dual of a certain kind of vielbein on the group manifold. The Yang–Mills fields include a torsion on space‐time.

On Application Of The Method Of Kinetic Invariants To The Description Of Dissolution Accompanied By A Chemical Reaction

The dissolution, accompanied by chemical reaction, of monodisperse solid particles has been analysed. The resulting model, which accounts for the variation of mass transfer coefficient with the size of the dissolving particles, yields an approximate analytical form of a kinetic function. Rigorous numerical and approximate analytical solutions have been obtained for the governing system of nonlinear ordinary differential equations. The transient nature of the dissolution process as well as the accuracy of the analytical solution is brought out by the rigorous numerical solution. The analytical solution is fairly accurate for the major part of the range of operational times encountered in practice.

A method for Estimating the Degree of Uncertainty With Respect to Life Cycle Assessment During Design

Life cycle assessment (LCA) is used to estimate a product's environmental impact. Using LCA during the earlier stages of design may produce erroneous results since information available on the product's lifecycle is typically incomplete at these stages. The resulting uncertainty must be accounted for in the decision-making process. This paper proposes a method for estimating the environmental impact of a product's life cycle and the associated degree of uncertainty of that impact using information generated during the design process. Total impact is estimated based on aggregation of individual product life cycle processes impacts. Uncertainty estimation is based on assessing the mismatch between the information required and the information available about the product life cycle in each uncertainty category, as well as their integration. The method is evaluated using pre-defined scenarios with varying uncertainty. DOI: 10.1115/1.4002163]

Narrowband random excitation of a limit cycle system

The response of the Van der Pol oscillator to stationary narrowband Gaussian excitation is considered. The central frequency of excitation is taken to be in the neighborhood of the system limit cycle frequency. The solution is obtained using a non-Gaussian closure approximation on the probability density function of the response. The validity of the solution is examined with the help of a stochastic stability analysis. Solution based on Stratonovich''s quasistatic averaging technique is also obtained. The comparison of the theoretical solutions with the digital simulations shows that the theoretical estimates are reasonably good.

A standard reference frame for the description of Nucleic Acid Base-Pair Geometry

A common point of reference is needed to describe the three-dimensional arrangements of bases and base-pairs in nucleic acid structures. The different standards used in computer programs created for this purpose give rise to con¯icting interpretations of the same structure.1 For example, parts of a structure that appear ``normal'' according to one computational scheme may be highly unusual according to another and vice versa. It is thus dif®cult to carry out comprehensive comparisons of nucleic acid structures and to pinpoint unique conformational features in individual structures

Molecular theory of ion solvation dynamics in water, acetonitrile and methanol: A unified microscopic description of collective dynamics in dipolar liquids

A recently developed microscopic theory of solvation dynamics in real dipolar liquids is used to calculate, for the first time, the solvation time correlation function in liquid acetonitrile, water and methanol. The calculated results are in excellent agreement with known experimental and computer simulation studies.