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.

Strength of lime-fly ash compacts using different curing techniques and gypsum additive

Lime-fly ash mixtures are exploited for the manufacture of fly ash bricks finding applications in load bearing masonry. Lime-pozzolana reactions take place at a slow pace under ambient temperature conditions and hence very long curing durations are required to achieve meaningful strength values. The present investigation examines the improvements in strength development in lime-fly ash compacts through low temperature steam curing and use of additives like gypsum. Results of density-strength-moulding water content relationships, influence of lime-fly ash ratio, steam curing and role of gypsum on strength development, and characteristics of compacted lime-fly ash-gypsum bricks have been discussed. The test results reveal that (a) strength increases with increase in density irrespective of lime content, type of curing and moulding water content, (b) optimum lime-fly ash ratio yielding maximum strength is about 0.75 in the normal curing conditions, (c) 24 h of steam curing (at 80A degrees C) is sufficient to achieve nearly possible maximum strength, (d) optimum gypsum content yielding maximum compressive strength is at 2%, (e) with gypsum additive it is possible to obtain lime-fly ash bricks or blocks having sufficient strength (> 10 MPa) at 28 days of normal wet burlap curing.

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.

Efficient algorithms for domination and Hamilton circuit problems on permutation graphs

The domination and Hamilton circuit problems are of interest both in algorithm design and complexity theory. The domination problem has applications in facility location and the Hamilton circuit problem has applications in routing problems in communications and operations research.The problem of deciding if G has a dominating set of cardinality at most k, and the problem of determining if G has a Hamilton circuit are NP-Complete. Polynomial time algorithms are, however, available for a large number of restricted classes. A motivation for the study of these algorithms is that they not only give insight into the characterization of these classes but also require a variety of algorithmic techniques and data structures. So the search for efficient algorithms, for these problems in many classes still continues.A class of perfect graphs which is practically important and mathematically interesting is the class of permutation graphs. The domination problem is polynomial time solvable on permutation graphs. Algorithms that are already available are of time complexity O(n2) or more, and space complexity O(n2) on these graphs. The Hamilton circuit problem is open for this class.We present a simple O(n) time and O(n) space algorithm for the domination problem on permutation graphs. Unlike the existing algorithms, we use the concept of geometric representation of permutation graphs. Further, exploiting this geometric notion, we develop an O(n2) time and O(n) space algorithm for the Hamilton circuit problem.

Perturbation expansions and series acceleration procedures: Part-II. Extrapolation techniques

Three new procedures for the extrapolation of series coefficients from a given power series expansion are proposed. They are based on (i) a novel resummation identity, (ii) parametrised Euler transformation (pet) and (iii) a modifiedpet. Several examples taken from the Ising model series expansions, ferrimagnetic systems, etc., are illustrated. Apart from these applications, the higher order virial coefficients for hard spheres and hard discs have also been evaluated using the new techniques and these are compared with the estimates obtained by other methods. A satisfactory agreement is revealed between the two.

Review of continuum, finite element and hybrid techniques in the analysis of stress concentrations in structures

When a uniform flow of any nature is interrupted, the readjustment of the flow results in concentrations and rare-factions, so that the peak value of the flow parameter will be higher than that which an elementary computation would suggest. When stress flow in a structure is interrupted, there are stress concentrations. These are generally localized and often large, in relation to the values indicated by simple equilibrium calculations. With the advent of the industrial revolution, dynamic and repeated loading of materials had become commonplace in engine parts and fast moving vehicles of locomotion. This led to serious fatigue failures arising from stress concentrations. Also, many metal forming processes, fabrication techniques and weak-link type safety systems benefit substantially from the intelligent use or avoidance, as appropriate, of stress concentrations. As a result, in the last 80 years, the study and and evaluation of stress concentrations has been a primary objective in the study of solid mechanics. Exact mathematical analysis of stress concentrations in finite bodies presents considerable difficulty for all but a few problems of infinite fields, concentric annuli and the like, treated under the presumption of small deformation, linear elasticity. A whole series of techniques have been developed to deal with different classes of shapes and domains, causes and sources of concentration, material behaviour, phenomenological formulation, etc. These include real and complex functions, conformal mapping, transform techniques, integral equations, finite differences and relaxation, and, more recently, the finite element methods. With the advent of large high speed computers, development of finite element concepts and a good understanding of functional analysis, it is now, in principle, possible to obtain with economy satisfactory solutions to a whole range of concentration problems by intelligently combining theory and computer application. An example is the hybridization of continuum concepts with computer based finite element formulations. This new situation also makes possible a more direct approach to the problem of design which is the primary purpose of most engineering analyses. The trend would appear to be clear: the computer will shape the theory, analysis and design.

Hybrid algorithms for power system unit commitment

Four hybrid algorithms has been developed for the solution of the unit commitment problem. They use simulated annealing as one of the constituent techniques, and produce lower cost schedules; two of them have less overhead than other soft computing techniques. They are also more robust to the choice of parameters. A special technique avoids the generating of infeasible schedules, and thus reduces computation time.

A risk-estimation-based formulation for speech enhancement and its relation to Wiener filtering

The goal of speech enhancement algorithms is to provide an estimate of clean speech starting from noisy observations. The often-employed cost function is the mean square error (MSE). However, the MSE can never be computed in practice. Therefore, it becomes necessary to find practical alternatives to the MSE. In image denoising problems, the cost function (also referred to as risk) is often replaced by an unbiased estimator. Motivated by this approach, we reformulate the problem of speech enhancement from the perspective of risk minimization. Some recent contributions in risk estimation have employed Stein's unbiased risk estimator (SURE) together with a parametric denoising function, which is a linear expansion of threshold/bases (LET). We show that the first-order case of SURE-LET results in a Wiener-filter type solution if the denoising function is made frequency-dependent. We also provide enhancement results obtained with both techniques and characterize the improvement by means of local as well as global SNR calculations.

Quantitative Strain and Compositional Studies of InxGa1-xAs Epilayer in a GaAs-based pHEMT Device Structure by TEM Techniques

In GaAs-based pseudomorphic high-electron mobility transistor device structures, strain and composition of the InxGa1 (-) As-x channel layer are very important as they influence the electronic properties of these devices. In this context, transmission electron microscopy techniques such as (002) dark-field imaging, high-resolution transmission electron microscopy (HRTEM) imaging, scanning transmission electron microscopy-high angle annular dark field (STEM-HAADF) imaging and selected area diffraction, are useful. A quantitative comparative study using these techniques is relevant for assessing the merits and limitations of the respective techniques. In this article, we have investigated strain and composition of the InxGa1 (-) As-x layer with the mentioned techniques and compared the results. The HRTEM images were investigated with strain state analysis. The indium content in this layer was quantified by HAADF imaging and correlated with STEM simulations. The studies showed that the InxGa1 (-) As-x channel layer was pseudomorphically grown leading to tetragonal strain along the 001] growth direction and that the average indium content (x) in the epilayer is similar to 0.12. We found consistency in the results obtained using various methods of analysis.

The hemispheric asymmetry of solar activity during the last century and the solar dynamo

We believe the Babcock-Leighton process of poloidal field generation to be the main source of irregularity in the solar cycle. The random nature of this process may make the poloidal field in one hemisphere stronger than that in the other hemisphere at the end of a cycle. We expect this to induce an asymmetry in the next sunspot cycle. We look for evidence of this in the observational data and then model it theoretically with our dynamo code. Since actual polar field measurements exist only from the 1970s, we use the polar faculae number data recorded by Sheeley (1991, 2008) as a proxy of the polar field and estimate the hemispheric asymmetry of the polar field in different solar minima during the major part of the twentieth century. This asymmetry is found to have a reasonable correlation with the asymmetry of the next cycle. We then run our dynamo code by feeding information about this asymmetry at the successive minima and compare the results with observational data. We find that the theoretically computed asymmetries of different cycles compare favorably with the observational data, with the correlation coefficient being 0.73. Due to the coupling between the two hemispheres, any hemispheric asymmetry tends to get attenuated with time. The hemispheric asymmetry of a cycle either from observational data or from theoretical calculations statistically tends to be less than the asymmetry in the polar field (as inferred from the faculae data) in the preceding minimum. This reduction factor turns out to be 0.43 and 0.51 respectively in observational data and theoretical simulations.

Optimal simultaneous maximum a posterioriestimation of states, noise statistics and parameters I. Algorithm

The simultaneous state and parameter estimation problem for a linear discrete-time system with unknown noise statistics is treated as a large-scale optimization problem. The a posterioriprobability density function is maximized directly with respect to the states and parameters subject to the constraint of the system dynamics. The resulting optimization problem is too large for any of the standard non-linear programming techniques and hence an hierarchical optimization approach is proposed. It turns out that the states can be computed at the first levelfor given noise and system parameters. These, in turn, are to be modified at the second level.The states are to be computed from a large system of linear equations and two solution methods are considered for solving these equations, limiting the horizon to a suitable length. The resulting algorithm is a filter-smoother, suitable for off-line as well as on-line state estimation for given noise and system parameters. The second level problem is split up into two, one for modifying the noise statistics and the other for modifying the system parameters. An adaptive relaxation technique is proposed for modifying the noise statistics and a modified Gauss-Newton technique is used to adjust the system parameters.

Crystal structure and conformation of the cyclic dipeptide cyclo-(L-histidyl-L-aspartyl) trihydrate

The crystal structure of cyclo-(L-histidyl-L-aspartyl) trihydrate has been determined by x-ray diffraction techniques, and refined to a final R index of 0.056 for 1601 reflections. The molecule is in a folded conformation, with the imidazole ring facing the diketopiperazine ring. However, since the diketopiperazine ring is essentially planar, the interaction between the two rings is not as intimate as in those cyclic dipeptides in which the diketopiperazine ring is in a boat conformation with the side chain occupying an axial, or flagpole, site. Planarity of the diketopiperazine ring may be dictated by steric interactions between the imidazole ring and the aspartyl side chain. The molecule is a zwitterion, a proton having been transferred from the carboxyl group of the aspartyl side chain to the imidazole ring.

Deformation and stability regression models for soil nail walls

Lateral displacement and global stability are the two main stability criteria for soil nail walls. Conventional design methods do not adequately address the deformation behaviour of soil nail walls, owing to the complexity involved in handling a large number of influencing factors. Consequently, limited methods of deformation estimates based on empirical relationships and in situ performance monitoring are available in the literature. It is therefore desirable that numerical techniques and statistical methods are used in order to gain a better insight into the deformation behaviour of soil nail walls. In the present study numerical experiments are conducted using a 2 4 factorial design method. Based on analysis of the maximum lateral deformation and factor-of-safety observations from the numerical experiments, regression models for maximum lateral deformation and factor-of-safety prediction are developed and checked for adequacy. Selection of suitable design factors for the 2 4 factorial design of numerical experiments enabled the use of the proposed regression models over a practical range of soil nail wall heights and in situ soil variability. It is evident from the model adequacy analyses and illustrative example that the proposed regression models provided a reasonably good estimate of the lateral deformation and global factor of safety of the soil nail walls.