Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance

We present two online algorithms for maintaining a topological order of a directed n-vertex acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm handles m arc additions in O(m(3/2)) time. For sparse graphs (m/n = O(1)), this bound improves the best previous bound by a logarithmic factor, and is tight to within a constant factor among algorithms satisfying a natural locality property. Our second algorithm handles an arbitrary sequence of arc additions in O(n(5/2)) time. For sufficiently dense graphs, this bound improves the best previous bound by a polynomial factor. Our bound may be far from tight: we show that the algorithm can take Omega(n(2)2 root(2lgn)) time by relating its performance to a generalization of the k-levels problem of combinatorial geometry. A completely different algorithm running in Theta (n(2) log n) time was given recently by Bender, Fineman, and Gilbert. We extend both of our algorithms to the maintenance of strong components, without affecting the asymptotic time bounds.

Spacelike pion form factor from analytic continuation and the onset of perturbative QCD

The factorization theorem for exclusive processes in perturbative QCD predicts the behavior of the pion electromagnetic form factor F(t) at asymptotic spacelike momenta t(= -Q(2)) < 0. We address the question of the onset energy using a suitable mathematical framework of analytic continuation, which uses as input the phase of the form factor below the first inelastic threshold, known with great precision through the Fermi-Watson theorem from pi pi elastic scattering, and the modulus measured from threshold up to 3 GeV by the BABAR Collaboration. The method leads to almost model-independent upper and lower bounds on the spacelike form factor. Further inclusion of the value of the charge radius and the experimental value at -2.45 GeV2 measured at JLab considerably increases the strength of the bounds in the region Q(2) less than or similar to 10 GeV2, excluding the onset of the asymptotic perturbative QCD regime for Q(2) < 7 GeV2. We also compare the bounds with available experimental data and with several theoretical models proposed for the low and intermediate spacelike region.

The Treewidth of MDS and Reed-Muller Codes

The constraint complexity of a graphical realization of a linear code is the maximum dimension of the local constraint codes in the realization. The treewidth of a linear code is the least constraint complexity of any of its cycle-free graphical realizations. This notion provides a useful parameterization of the maximum-likelihood decoding complexity for linear codes. In this paper, we show the surprising fact that for maximum distance separable codes and Reed-Muller codes, treewidth equals trelliswidth, which, for a code, is defined to be the least constraint complexity (or branch complexity) of any of its trellis realizations. From this, we obtain exact expressions for the treewidth of these codes, which constitute the only known explicit expressions for the treewidth of algebraic codes.

The Kπ form factors from analyticity and unitarity

Analyticity and unitarity techniques are employed to obtain bounds on the shape parameters of the scalar and vector form factors of semileptonic K l3 decays. For this purpose we use vector and scalar correlators evaluated in pQCD, a low energy theorem for scalar form factor, lattice results for the ratio of kaon and pion decay constants, chiral perturbation theory calculations for the scalar form factor at the Callan-Treiman point and experimental information on the phase and modulus of Kπ form factors up to an energy t in = 1GeV 2. We further derive regions on the real axis and in the complex-energy plane where the form factors cannot have zeros.

Constraining form factors with the method of unitarity bounds

The availability of a reliable bound on an integral involving the square of the modulus of a form factor on the unitarity cut allows one to constrain the form factor at points inside the analyticity domain and its shape parameters, and also to isolate domains on the real axis and in the complex energy plane where zeros are excluded. In this lecture note, we review the mathematical techniques of this formalism in its standard form, known as the method of unitarity bounds, and recent developments which allow us to include information on the phase and modulus along a part of the unitarity cut. We also provide a brief summary of some results that we have obtained in the recent past, which demonstrate the usefulness of the method for precision predictions on the form factors.

Rainbow connection number and connected dominating sets

The rainbow connection number of a connected graph is the minimum number of colors needed to color its edges, so that every pair of its vertices is connected by at least one path in which no two edges are colored the same. In this article we show that for every connected graph on n vertices with minimum degree delta, the rainbow connection number is upper bounded by 3n/(delta + 1) + 3. This solves an open problem from Schiermeyer (Combinatorial Algorithms, Springer, Berlin/Hiedelberg, 2009, pp. 432437), improving the previously best known bound of 20n/delta (J Graph Theory 63 (2010), 185191). This bound is tight up to additive factors by a construction mentioned in Caro et al. (Electr J Combin 15(R57) (2008), 1). As an intermediate step we obtain an upper bound of 3n/(delta + 1) - 2 on the size of a connected two-step dominating set in a connected graph of order n and minimum degree d. This bound is tight up to an additive constant of 2. This result may be of independent interest. We also show that for every connected graph G with minimum degree at least 2, the rainbow connection number, rc(G), is upper bounded by Gc(G) + 2, where Gc(G) is the connected domination number of G. Bounds of the form diameter(G)?rc(G)?diameter(G) + c, 1?c?4, for many special graph classes follow as easy corollaries from this result. This includes interval graphs, asteroidal triple-free graphs, circular arc graphs, threshold graphs, and chain graphs all with minimum degree delta at least 2 and connected. We also show that every bridge-less chordal graph G has rc(G)?3.radius(G). In most of these cases, we also demonstrate the tightness of the bounds.

Theory and Algorithms for Hop-Count-Based Localization with Random Geometric Graph Models of Dense Sensor Networks

Wireless sensor networks can often be viewed in terms of a uniform deployment of a large number of nodes in a region of Euclidean space. Following deployment, the nodes self-organize into a mesh topology with a key aspect being self-localization. Having obtained a mesh topology in a dense, homogeneous deployment, a frequently used approximation is to take the hop distance between nodes to be proportional to the Euclidean distance between them. In this work, we analyze this approximation through two complementary analyses. We assume that the mesh topology is a random geometric graph on the nodes; and that some nodes are designated as anchors with known locations. First, we obtain high probability bounds on the Euclidean distances of all nodes that are h hops away from a fixed anchor node. In the second analysis, we provide a heuristic argument that leads to a direct approximation for the density function of the Euclidean distance between two nodes that are separated by a hop distance h. This approximation is shown, through simulation, to very closely match the true density function. Localization algorithms that draw upon the preceding analyses are then proposed and shown to perform better than some of the well-known algorithms present in the literature. Belief-propagation-based message-passing is then used to further enhance the performance of the proposed localization algorithms. To our knowledge, this is the first usage of message-passing for hop-count-based self-localization.

Constraints on the Kl3 form factors from analyticity and unitarity

The K pi form factors are investigated at low energies by the method of unitarity bounds adapted so as to include information on the phase and modulus along the elastic region of the unitarity cut. Using as input the values of the form factors at t = 0, and at the Callan-Treiman point in the scalar case, stringent constraints are obtained on the slope and curvature parameters of the Taylor expansion at the origin.

Model independent bounds on the modulus of the pion form factor on the unitarity cut below the omega pi threshold

We calculate upper and lower bounds on the modulus of the pion electromagnetic form factor on the unitarity cut below the omega pi inelastic threshold, using as input the phase in the elastic region known via the Fermi-Watson theorem from the pi pi P-wave phase shift, and a suitably weighted integral of the modulus squared above the inelastic threshold. The normalization at t = 0, the pion charge radius and experimental values at spacelike momenta are used as additional input information. The bounds are model independent, in the sense that they do not rely on specific parametrizations and do not require assumptions on the phase of the form factor above the inelastic threshold. The results provide nontrivial consistency checks on the recent experimental data on the modulus available below the omega pi threshold from e(+)e(-) annihilation and tau-decay experiments. In particular, at low energies the calculated bounds offer a more precise description of the modulus than the experimental data.

Generalizing the Amplify-and-Forward Relay Gain Model: An Optimal SEP Perspective

Two models for AF relaying, namely, fixed gain and fixed power relaying, have been extensively studied in the literature given their ability to harness spatial diversity. In fixed gain relaying, the relay gain is fixed but its transmit power varies as a function of the source-relay channel gain. In fixed power relaying, the relay transmit power is fixed, but its gain varies. We revisit and generalize the fundamental two-hop AF relaying model. We present an optimal scheme in which an average power constrained AF relay adapts its gain and transmit power to minimize the symbol error probability (SEP) at the destination. Also derived are insightful and practically amenable closed-form bounds for the optimal relay gain. We then analyze the SEP of MPSK, derive tight bounds for it, and characterize the diversity order for Rayleigh fading. Also derived is an SEP approximation that is accurate to within 0.1 dB. Extensive results show that the scheme yields significant energy savings of 2.0-7.7 dB at the source and relay. Optimal relay placement for the proposed scheme is also characterized, and is different from fixed gain or power relaying. Generalizations to MQAM and other fading distributions are also discussed.

Cubicity and Bandwidth

A unit cube in (or a k-cube in short) is defined as the Cartesian product R (1) x R (2) x ... x R (k) where R (i) (for 1 a parts per thousand currency sign i a parts per thousand currency sign k) is a closed interval of the form a (i) , a (i) + 1] on the real line. A k-cube representation of a graph G is a mapping of the vertices of G to k-cubes such that two vertices in G are adjacent if and only if their corresponding k-cubes have a non-empty intersection. The cubicity of G is the minimum k such that G has a k-cube representation. From a geometric embedding point of view, a k-cube representation of G = (V, E) yields an embedding such that for any two vertices u and v, ||f(u) - f(v)||(a) a parts per thousand currency sign 1 if and only if . We first present a randomized algorithm that constructs the cube representation of any graph on n vertices with maximum degree Delta in O(Delta ln n) dimensions. This algorithm is then derandomized to obtain a polynomial time deterministic algorithm that also produces the cube representation of the input graph in the same number of dimensions. The bandwidth ordering of the graph is studied next and it is shown that our algorithm can be improved to produce a cube representation of the input graph G in O(Delta ln b) dimensions, where b is the bandwidth of G, given a bandwidth ordering of G. Note that b a parts per thousand currency sign n and b is much smaller than n for many well-known graph classes. Another upper bound of b + 1 on the cubicity of any graph with bandwidth b is also shown. Together, these results imply that for any graph G with maximum degree Delta and bandwidth b, the cubicity is O(min{b, Delta ln b}). The upper bound of b + 1 is used to derive upper bounds for the cubicity of circular-arc graphs, cocomparability graphs and AT-free graphs in terms of the maximum degree Delta.

Cramer-Rao-Type Bounds for Sparse Bayesian Learning

In this paper, we derive Hybrid, Bayesian and Marginalized Cramer-Rao lower bounds (HCRB, BCRB and MCRB) for the single and multiple measurement vector Sparse Bayesian Learning (SBL) problem of estimating compressible vectors and their prior distribution parameters. We assume the unknown vector to be drawn from a compressible Student-prior distribution. We derive CRBs that encompass the deterministic or random nature of the unknown parameters of the prior distribution and the regression noise variance. We extend the MCRB to the case where the compressible vector is distributed according to a general compressible prior distribution, of which the generalized Pareto distribution is a special case. We use the derived bounds to uncover the relationship between the compressibility and Mean Square Error (MSE) in the estimates. Further, we illustrate the tightness and utility of the bounds through simulations, by comparing them with the MSE performance of two popular SBL-based estimators. We find that the MCRB is generally the tightest among the bounds derived and that the MSE performance of the Expectation-Maximization (EM) algorithm coincides with the MCRB for the compressible vector. We also illustrate the dependence of the MSE performance of SBL based estimators on the compressibility of the vector for several values of the number of observations and at different signal powers.

Realistic minimum desorption temperatures and compressor sizing for activated carbon + HFC 134a adsorption coolers

A low thermal diffusivity of adsorption beds induces a large thermal gradient across cylindrical adsorbers used in adsorption cooling cycles. This reduces the concentration difference across which a thermal compressor operates. Slow adsorption kinetics in conjunction with the void volume effect further diminishes throughputs from those adsorption thermal compressors. The problem can be partially alleviated by increasing the desorption temperatures. The theme of this paper is the determination the minimum desorption temperature required for a given set of evaporating/condensing temperatures for an activated carbon + HFC 134a adsorption cooler. The calculation scheme is validated from experimental data. Results from a parametric analysis covering a range of evaporating/condensing/desorption temperatures are presented. It is found that the overall uptake efficiency and Carnot COP characterize these bounds. A design methodology for adsorber sizing is evolved. (c) 2012 Elsevier Ltd. All rights reserved.

Quantitative interactions between the A-type K+ current and inositol trisphosphate receptors regulate intraneuronal Ca2+ waves and synaptic plasticity

Key points center dot Active calcium signal propagation occurs when an initial calcium trigger elicits calcium release through endoplasmic reticulum (ER) receptors. A high concentration of the calcium trigger in thin-calibre dendrites would suppress release of calcium through hippocampal inositol trisphosphate receptors (InsP3Rs). center dot Could the high-density expression of A-type K+ channels in thin-calibre dendrites be a mechanism for inhibiting this suppression, thereby restoring the utility of the ER as a substrate for active calcium propagation? center dot Quantitative analyses involving experimentally constrained models reveal a bell-shaped dependence of calcium released through InsP3Rs on the A-type K+ channel density, during the propagation of a calcium wave. center dot A-type K+ channels regulated the relative contribution of ER calcium to the induction of synaptic plasticity in the presence of model metabotropic glutamate receptors. center dot These results identify a novel form of interaction between active dendrites and the ER membrane and suggest that A-type K+ channels are ideally placed for inhibiting the suppression of InsP3Rs in thin-calibre dendrites. Abstract The A-type potassium current has been implicated in the regulation of several physiological processes. Here, we explore a role for the A-type potassium current in regulating the release of calcium through inositol trisphosphate receptors (InsP3R) that reside on the endoplasmic reticulum (ER) of hippocampal pyramidal neurons. To do this, we constructed morphologically realistic, conductance-based models equipped with kinetic schemes that govern several calcium signalling modules and pathways, and constrained the distributions and properties of constitutive components by experimental measurements from these neurons. Employing these models, we establish a bell-shaped dependence of calcium release through InsP3Rs on the density ofA-type potassium channels, during the propagation of an intraneuronal calcium wave initiated through established protocols. Exploring the sensitivities of calcium wave initiation and propagation to several underlying parameters, we found that ER calcium release critically depends on dendritic diameter and that wave initiation occurred at branch points as a consequence of a high surface area to volume ratio of oblique dendrites. Furthermore, analogous to the role ofA-type potassium channels in regulating spike latency, we found that an increase in the density ofA-type potassium channels led to increases in the latency and the temporal spread of a propagating calcium wave. Next, we incorporated kinetic models for the metabotropic glutamate receptor (mGluR) signalling components and a calcium-controlled plasticity rule into our model and demonstrate thatthe presence of mGluRs induced a leftward shift in a BienenstockCooperMunro-like synaptic plasticity profile. Finally, we show that the A-type potassium current could regulate the relative contribution of ER calcium to synaptic plasticity induced either through 900 pulses of various stimulus frequencies or through theta burst stimulation. Our results establish a novel form of interaction between active dendrites and the ER membrane, uncovering a powerful mechanism that could regulate biophysical/biochemical signal integration and steer the spatiotemporal spread of signalling microdomains through changes in dendritic excitability.

Evidence for the role of Mycobacteriumtuberculosis RecG helicase in DNA repair and recombination

In order to survive and replicate in a variety of stressful conditions during its life cycle, Mycobacteriumtuberculosis must possess mechanisms to safeguard the integrity of the genome. Although DNA repair and recombination related genes are thought to play key roles in the repair of damaged DNA in all organisms, so far only a few of them have been functionally characterized in the tubercle bacillus. In this study, we show that M.tuberculosis RecG (MtRecG) expression was induced in response to different genotoxic agents. Strikingly, expression of MtRecG in Escherichiacoli recG mutant strain provided protection against mitomycin C, methyl methane sulfonate and UV induced cell death. Purified MtRecG exhibited higher binding affinity for the Holliday junction (HJ) compared with a number of canonical recombinational DNA repair intermediates. Notably, although MtRecG binds at the core of the mobile and immobile HJs, and with higher binding affinity for the immobile HJ, branch migration was evident only in the case of the mobile HJ. Furthermore, immobile HJs stimulate MtRecG ATPase activity less efficiently than mobile HJs. In addition to HJ substrates, MtRecG exhibited binding affinity for a variety of branched DNA structures including three-way junctions, replication forks, flap structures, forked duplex and a D-loop structure, but demonstrated strong unwinding activity on replication fork and flap DNA structures. Together, these results support that MtRecG plays an important role in processes related to DNA metabolism under normal as well as stress conditions.