Studies on nucleotidases in plants Dimerization of the crystalline mung bean nucleotide pyrophosphatase by 5-adenosine monophosphate and the properties of the dimerized enzyme

The addition of AMP to the crystalline and homogeneous mung bean nucleotide pyrophosphatase [EC 3.6.1.9]altered its electrophoretic mobility. AMP was tightly bound to the enzyme and was not removed on passage through a column of Sephadex G-25 or on electrophoresis. The molecular weight of the native and AMP-modified enzymes were 65,000 and 136,000, respectively. The properties of the native enzyme such as the pH (9.4) and temperature (49 °C) optima, inhibition by EDTA, reversal of EDTA-inhibition by Zn2+ and Co2+, were not altered on dimerization by AMP. The AMP-modified enzyme had a linear time-course of reaction, unlike the native enzyme which exhibited a biphasic time-course of reaction. The AMP-modified enzyme was irreversibly denatured by urea. AMP concentrations larger than 100 μM inhibited linearly the activity of the AMP-modified enzyme. ADP and ATP inhibited the activity in a sigmoidal manner. Km and V of the native and AMP-modified enzymes were, 0.25 mImage and 0.58 mImage ; and 3.3 and 2.5, respectively.

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.

A particle filtering approach for structural system identification in vehicle–structure interaction problems

The problem of identification of parameters of a beam-moving oscillator system based on measurement of time histories of beam strains and displacements is considered. The governing equations of motion here have time varying coefficients. The parameters to be identified are however time invariant and consist of mass, stiffness and damping characteristics of the beam and oscillator subsystems. A strategy based on dynamic state estimation method, that employs particle filtering algorithms, is proposed to tackle the identification problem. The method can take into account measurement noise, guideway unevenness, spatially incomplete measurements, finite element models for supporting structure and moving vehicle, and imperfections in the formulation of the mathematical models. Numerical illustrations based on synthetic data on beam-oscillator system are presented to demonstrate the satisfactory performance of the proposed procedure.

A new class of separators and planarity of chordal graphs

We introduce a new class of clique separators, called base sets, for chordal graphs. Base sets of a chordal graph closely reflect its structure. We show that the notion of base sets leads to structural characterizations of planar k-trees and planar chordal graphs. Using these characterizations, we develop linear time algorithms for recognizing planar k-trees and planar chordal graphs. These algorithms are extensions of the Lexicographic_Breadth_First_Search algorithm for recognizing chordal graphs and are much simpler than the general planarity checking algorithm. Further, we use the notion of base sets to prove the equivalence of hamiltonian 2-trees and maximal outerplanar graphs.

Utilization bounds for RM scheduling on uniform multiprocessors

Utilization bounds for Earliest Deadline First(EDF) and Rate Monotonic(RM) scheduling are known and well understood for uniprocessor systems. In this paper, we derive limits on similar bounds for the multiprocessor case, when the individual processors need not be identical. Tasks are partitioned among the processors and RM scheduling is assumed to be the policy used in individual processors. A minimum limit on the bounds for a 'greedy' class of algorithms is given and proved, since the actual value of the bound depends on the algorithm that allocates the tasks. We also derive the utilization bound of an algorithm which allocates tasks in decreasing order of utilization factors. Knowledge of such bounds allows us to carry out very fast schedulability tests although we are constrained by the fact that the tests are sufficient but not necessary to ensure schedulability.

Studies on nucleotidases in plants: Fluorescence and kinetic properties of nucleotide pyrophosphatase from mung bean (Phaseolus aureus) seedlings

Nucleotide pyrophosphatase of mung bean seedlings has earlier been isolated in our laboratory in a dimeric form (Mr 65,000) and has been shown to be converted to a tetramer by AMP and to a monomer by p-hydroxymercuribenzoate. All the molecular forms were enzymatically active with different kinetic properties. By a modified procedure using blue-Sepharose affinity chromatography, we have now obtained a dimeric form of the enzyme which is desensitized to AMP interaction. The molecular weight of the desensitized form of the enzyme was found to be the same as that of the native dimeric enzyme. However, the desensitized enzyme functioned with a linear time course, contrary to the biphasic time course exhibited by the native enzyme. In addition, it was not converted to a tetramer on the addition of AMP, had only one binding site for adenine nucleotides, and p-hydroxy-mercuribenzoate had no effect on the time course of the reaction or on the molecular weight of the enzyme. The temperature optimum of the desensitized enzyme was found to be 67 °C in contrast to the optimum of 49 °C for the native dimer. Fifty percent of the tryptophan residues of the desensitized enzyme were not accessible for quenching by iodide. Fluorescence studies gave Kd values of 0.34, 2.2, and 0.8 mImage for AMP, ADP, and ATP, which were close to the Ki values of 0.12, 2.2, and 0.9 mImage , respectively, for these nucleotides. The binding and inhibition studies with AMP and its analogs showed that the 6-amino group and the 5′-phosphate group were essential for the inhibition of the enzyme activity.

Tree 3-spanners in 2-sep chordal graphs: Characterization and algorithms

A spanning tree T of a graph G is said to be a tree t-spanner if the distance between any two vertices in T is at most t times their distance in G. A graph that has a tree t-spanner is called a tree t-spanner admissible graph. The problem of deciding whether a graph is tree t-spanner admissible is NP-complete for any fixed t >= 4 and is linearly solvable for t <= 2. The case t = 3 still remains open. A chordal graph is called a 2-sep chordal graph if all of its minimal a - b vertex separators for every pair of non-adjacent vertices a and b are of size two. It is known that not all 2-sep chordal graphs admit tree 3-spanners This paper presents a structural characterization and a linear time recognition algorithm of tree 3-spanner admissible 2-sep chordal graphs. Finally, a linear time algorithm to construct a tree 3-spanner of a tree 3-spanner admissible 2-sep chordal graph is proposed. (C) 2010 Elsevier B.V. All rights reserved.

New Approximation Algorithms for Minimum Cycle Bases of Graphs

We consider the problem of computing an approximate minimum cycle basis of an undirected non-negative 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. Although in most such applications any cycle basis can be used, a low weight cycle basis often translates to better performance and/or numerical stability. Despite the fact that the problem can be solved exactly in polynomial time, we design approximation algorithms since the performance of the exact algorithms may be too expensive for some practical applications. 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 O(kmn(1+2/k) + mn((1+1/k)(omega-1))) and deterministic running time O(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 expected running time O(M-omega root n log n), 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.

Additive Spanners and (alpha, beta)-Spanners

An (alpha, beta)-spanner of an unweighted graph G is a subgraph H that distorts distances in G up to a multiplicative factor of a and an additive term beta. It is well known that any graph contains a (multiplicative) (2k - 1, 0)-spanner of size O(n(1+1/k)) and an (additive) (1, 2)-spanner of size O(n(3/2)). However no other additive spanners are known to exist. In this article we develop a couple of new techniques for constructing (alpha, beta)-spanners. Our first result is an additive (1, 6)-spanner of size O(n(4/3)). The construction algorithm can be understood as an economical agent that assigns costs and values to paths in the graph, purchasing affordable paths and ignoring expensive ones, which are intuitively well approximated by paths already purchased. We show that this path buying algorithm can be parameterized in different ways to yield other sparseness-distortion tradeoffs. Our second result addresses the problem of which (alpha, beta)-spanners can be computed efficiently, ideally in linear time. We show that, for any k, a (k, k - 1)-spanner with size O(kn(1+1/k)) can be found in linear time, and, further, that in a distributed network the algorithm terminates in a constant number of rounds. Previous spanner constructions with similar performance had roughly twice the multiplicative distortion.

Lazy structure sharing for query optimization

We study lazy structure sharing as a tool for optimizing equivalence testing on complex data types, We investigate a number of strategies for implementing lazy structure sharing and provide upper and lower bounds on their performance (how quickly they effect ideal configurations of our data structure). In most cases when the strategies are applied to a restricted case of the problem, the bounds provide nontrivial improvements over the naive linear-time equivalence-testing strategy that employs no optimization. Only one strategy, however, which employs path compression, seems promising for the most general case of the problem.

The existence of homeomorphic subgraphs in chordal graphs

We establish conditions for the existence, in a chordal graph, of subgraphs homeomorphic to K-n (n greater than or equal to 3), K-m,K-n (m,n greater than or equal to 2), and wheels W-r (r greater than or equal to 3). Using these results, we develop a simple linear time algorithm for testing planarity of chordal graphs. We also show how these results lead to simple polynomial time algorithms for the Fixed Subgraph Homeomorphism problem on chordal graphs for some special classes of pattern graphs.

An Optimized SDE Model for Slotted Aloha

We consider a stochastic differential equation (SDE) model of slotted Aloha with the retransmission probability as the associated parameter. We formulate the problem in both (a) the finite horizon and (b) the infinite horizon average cost settings. We apply the algorithm of 3] for the first setting, while for the second, we adapt a related algorithm from 2] that was originally developed in the simulation optimization framework. In the first setting, we obtain an optimal parameter trajectory that prescribes the parameter to use at any given instant while in the second setting, we obtain an optimal time-invariant parameter. Our algorithms are seen to exhibit good performance.

Continuous Recording of Retardation and Intensity of Echoes from the Ionosphere

Pulse retardation method of Breit and Tuve has been modified to record continuously the equivalent height as well as the intensity of reflections from the ionosphere. Synchronized pulses are transmitted, and the received ground pulse and the reflected pulses, after amplification and suitable distortion, are applied to the focusing cylinder of a cathode ray tube the horizontal deflecting plates of which are connected to a synchronized linear time base circuit. The pattern on the screen is composed of a bright straight line corresponding to the time base with dark gaps corresponding to the received pulses. The distance between the initial points of the gaps represents retardation while the widths of the gaps correspond to the intensity of the pulses. The pattern is photographed on a vertically moving film. One of the first few records taken at Bangalore on 4 megacycles is reproduced. It shows, among other things, that the less retarded component of magneto-ionic splitting from the F layer is present most of the time. Whenever the longer retardation component does occur, it has stronger intensity than the former. Towards the late evening hours, just before disappearing, when the F layer rises and exhibits magnetoionic splitting, the intensity of the less retarded component is extremely low compared with the other component.

Complexity of distance paired-domination problem in graphs

Suppose G = (V, E) is a simple graph and k is a fixed positive integer. A subset D subset of V is a distance k-dominating set of G if for every u is an element of V. there exists a vertex v is an element of D such that d(G)(u, v) <= k, where d(G)(u, v) is the distance between u and v in G. A set D subset of V is a distance k-paired-dominating set of G if D is a distance k-dominating set and the induced subgraph GD] contains a perfect matching. Given a graph G = (V, E) and a fixed integer k > 0, the MIN DISTANCE k-PAIRED-DOM SET problem is to find a minimum cardinality distance k-paired-dominating set of G. In this paper, we show that the decision version of MIN DISTANCE k-PAIRED-DOM SET iS NP-complete for undirected path graphs. This strengthens the complexity of decision version Of MIN DISTANCE k-PAIRED-DOM SET problem in chordal graphs. We show that for a given graph G, unless NP subset of DTIME (n(0)((log) (log) (n)) MIN DISTANCE k-PAIRED-Dom SET problem cannot be approximated within a factor of (1 -epsilon ) In n for any epsilon > 0, where n is the number of vertices in G. We also show that MIN DISTANCE k-PAIRED-DOM SET problem is APX-complete for graphs with degree bounded by 3. On the positive side, we present a linear time algorithm to compute the minimum cardinality of a distance k-paired-dominating set of a strongly chordal graph G if a strong elimination ordering of G is provided. We show that for a given graph G, MIN DISTANCE k-PAIRED-DOM SET problem can be approximated with an approximation factor of 1 + In 2 + k . In(Delta(G)), where Delta(G) denotes the maximum degree of G. (C) 2012 Elsevier B.V All rights reserved.

Representing a cubic graph as the intersection graph of axis-parallel boxes in three dimensions

We show that every graph of maximum degree 3 can be represented as the intersection graph of axis parallel boxes in three dimensions, that is, every vertex can be mapped to an axis parallel box such that two boxes intersect if and only if their corresponding vertices are adjacent. In fact, we construct a representation in which any two intersecting boxes just touch at their boundaries. Further, this construction can be realized in linear time.