Geometric Representation of Graphs in Low Dimension Using Axis Parallel Boxes

An axis-parallel k-dimensional box is a Cartesian product R-1 x R-2 x...x R-k where R-i (for 1 <= i <= k) is a closed interval of the form [a(i), b(i)] on the real line. For a graph G, its boxicity box(G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem for boxicity d graphs, given a box representation, has a left perpendicular1 + 1/c log n right perpendicular(d-1) approximation ratio for any constant c >= 1 when d >= 2. In most cases, the first step usually is computing a low dimensional box representation of the given graph. Deciding whether the boxicity of a graph is at most 2 itself is NP-hard. We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in left perpendicular(Delta + 2) ln nright perpendicular dimensions, where Delta is the maximum degree of G. This algorithm implies that box(G) <= left perpendicular(Delta + 2) ln nright perpendicular for any graph G. Our bound is tight up to a factor of ln n. We also show that our randomized algorithm can be derandomized to get a polynomial time deterministic algorithm. Though our general upper bound is in terms of maximum degree Delta, we show that for almost all graphs on n vertices, their boxicity is O(d(av) ln n) where d(av) is the average degree.

Time Domain Characteristics of Electrical Measures for a Piezoelectric Thin Film to Identify Defects in the Substrate

A reduced 3D continuum model of dynamic piezoelectricity in a thin-film surface-bonded to the substrate/host is presented in this article. While employing large area flexible thin piezoelectric films for novel applications in device/diagnostics, the feasibility of the proposed model in sensing the surface and/or sub-surface defects is demonstrated through simulations - which involve metallic beams with cracks and composite beam with delaminations of various sizes. We have introduced a set of electrical measures to capture the severity of the damage in the existing structures. Characteristics of these electrical measures in terms of the potential difference and its spatial gradients are illustrated in the time domain. Sensitivity studies of the proposed measures in terms of the defected areas and their region of occurence relative to the sensing film are reported. The simulations' results for electrical measures for damaged hosts/substrates are compared with those due to undamaged hosts/substrates, which show monotonicity with high degree of sensitivity to variations in the damage parameters.

A Slotted Aloha joint MAC-cum-Routing protocol for data gathering sensor network applications

In this paper we have proposed and implemented a joint Medium Access Control (MAC) -cum- Routing scheme for environment data gathering sensor networks. The design principle uses node 'battery lifetime' maximization to be traded against a network that is capable of tolerating: A known percentage of combined packet losses due to packet collisions, network synchronization mismatch and channel impairments Significant end-to-end delay of an order of few seconds We have achieved this with a loosely synchronized network of sensor nodes that implement Slotted-Aloha MAC state machine together with route information. The scheme has given encouraging results in terms of energy savings compared to other popular implementations. The overall packet loss is about 12%. The battery life time increase compared to B-MAC varies from a minimum of 30% to about 90% depending on the duty cycle.

A self-adaptive migration model genetic algorithm for data mining applications

Data mining involves nontrivial process of extracting knowledge or patterns from large databases. Genetic Algorithms are efficient and robust searching and optimization methods that are used in data mining. In this paper we propose a Self-Adaptive Migration Model GA (SAMGA), where parameters of population size, the number of points of crossover and mutation rate for each population are adaptively fixed. Further, the migration of individuals between populations is decided dynamically. This paper gives a mathematical schema analysis of the method stating and showing that the algorithm exploits previously discovered knowledge for a more focused and concentrated search of heuristically high yielding regions while simultaneously performing a highly explorative search on the other regions of the search space. The effective performance of the algorithm is then shown using standard testbed functions and a set of actual classification datamining problems. Michigan style of classifier was used to build the classifier and the system was tested with machine learning databases of Pima Indian Diabetes database, Wisconsin Breast Cancer database and few others. The performance of our algorithm is better than others.

Engineered protease inhibitors based on sunflower trypsin inhibitor-1 (SFTI-1) provide insights into the role of sequence and conformation in Laskowski mechanism inhibition

Laskowski inhibitors regulate serine proteases by an intriguing mode of action that involves deceiving the protease into synthesizing a peptide bond. Studies exploring naturally occurring Laskowski inhibitors have uncovered several structural features that convey the inhibitor's resistance to hydrolysis and exceptional binding affinity. However, in the context of Laskowski inhibitor engineering, the way that various modifications intended to fine-tune an inhibitor's potency and selectivity impact on its association and dissociation rates remains unclear. This information is important as Laskowski inhibitors are becoming increasingly used as design templates to develop new protease inhibitors for pharmaceutical applications. In this study, we used the cyclic peptide, sunflower trypsin inhibitor-1 (SFTI-1), as a model system to explore how the inhibitor's sequence and structure relate to its binding kinetics and function. Using enzyme assays, MD simulations and NMR spectroscopy to study SFTI variants with diverse sequence and backbone modifications, we show that the geometry of the binding loop mainly influences the inhibitor's potency by modulating the association rate, such that variants lacking a favourable conformation show dramatic losses in activity. Additionally, we show that the inhibitor's sequence (including both the binding loop and its scaffolding) influences its potency and selectivity by modulating both the association and the dissociation rates. These findings provide new insights into protease inhibitor function and design that we apply by engineering novel inhibitors for classical serine proteases, trypsin and chymotrypsin and two kallikrein-related peptidases (KLK5 and KLK14) that are implicated in various cancers and skin diseases.

Analytical models for capacity estimation of IEEE 802.11 WLANs using DCF for internet applications

We provide analytical models for capacity evaluation of an infrastructure IEEE 802.11 based network carrying TCP controlled file downloads or full-duplex packet telephone calls. In each case the analytical models utilize the attempt probabilities from a well known fixed-point based saturation analysis. For TCP controlled file downloads, following Bruno et al. (In Networking '04, LNCS 2042, pp. 626-637), we model the number of wireless stations (STAs) with ACKs as a Markov renewal process embedded at packet success instants. In our work, analysis of the evolution between the embedded instants is done by using saturation analysis to provide state dependent attempt probabilities. We show that in spite of its simplicity, our model works well, by comparing various simulated quantities, such as collision probability, with values predicted from our model. Next we consider N constant bit rate VoIP calls terminating at N STAs. We model the number of STAs that have an up-link voice packet as a Markov renewal process embedded at so called channel slot boundaries. Analysis of the evolution over a channel slot is done using saturation analysis as before. We find that again the AP is the bottleneck, and the system can support (in the sense of a bound on the probability of delay exceeding a given value) a number of calls less than that at which the arrival rate into the AP exceeds the average service rate applied to the AP. Finally, we extend the analytical model for VoIP calls to determine the call capacity of an 802.11b WLAN in a situation where VoIP calls originate from two different types of coders. We consider N-1 calls originating from Type 1 codecs and N-2 calls originating from Type 2 codecs. For G711 and G729 voice coders, we show that the analytical model again provides accurate results in comparison with simulations.

Interrupted creep behaviour of Mg alloys developed for powertrain applications

A conventional magnesium alloy, AZ91D, and two creep resistant magnesium alloys, developed for powertrain applications, MRI 153M and MRI 230D, are prepared by high pressure die casting. These alloys are tested for their creep behaviour in the continuous manner, as is the Current practice, and in the interrupted manner, which represents the real life Situation more closely. It is observed that the interrupted creep tests give rise to a primary creep appearing at the beginning of each cycle resulting in a higher average strain rate than that encountered in the continuous creep tests. Further, the shorter the cycle time, higher is the average strain rate in the interrupted creep tests. A higher average strain rate will give rise to a higher strain over the same period. This is attributed to the recovery taking place during the cooling and heating between two cycles. The effect of additional precipitation during interrupted creep tests depends on the nature of the precipitates. The additional precipitation of beta phase during the cooling and heating between two cycles increases the steady state strain rate in the AZ91D and MRI 153M alloys. whereas the additional precipitation of C36 phase during the cooling and heating between two cycles decreases the steady state strain rate in the MRI 230D alloy. (C) 2009 Elsevier B.V. All rights reserved.

Physical properties of meteorites and their role in planetology

Together with cosmic spherules, interplanetary dust particles and lunar samples returned by Apollo and Luna missions, meteorites are the only source of extraterrestrial material on Earth. The physical properties of meteorites, especially their magnetic susceptibility, bulk and grain density, porosity and paleomagnetic information, have wide applications in planetary research and can reveal information about origin and internal structure of asteroids. Thus, an expanded database of meteorite physical properties was compiled with new measurements done in meteorite collections across Europe using a mobile laboratory facility. However, the scale problem may bring discrepancies in the comparison of asteroid and meteorite properties. Due to inhomogenity, the physical properties of meteorites studied on a centimeter or millimeter scale may differ from those of asteroids determined on kilometer scales. Further difference may arise from shock effects, space and terrestrial weathering and from difference in material properties at various temperatures. Close attention was given to the reliability of the paleomagnetic and paleointensity information in meteorites and the methodology to test for magnetic overprints was prepared and verified.

Adaptive tree multigrids and simplified spherical harmonics approximation in deterministic neutral and charged particle transport

A new deterministic three-dimensional neutral and charged particle transport code, MultiTrans, has been developed. In the novel approach, the adaptive tree multigrid technique is used in conjunction with simplified spherical harmonics approximation of the Boltzmann transport equation. The development of the new radiation transport code started in the framework of the Finnish boron neutron capture therapy (BNCT) project. Since the application of the MultiTrans code to BNCT dose planning problems, the testing and development of the MultiTrans code has continued in conventional radiotherapy and reactor physics applications. In this thesis, an overview of different numerical radiation transport methods is first given. Special features of the simplified spherical harmonics method and the adaptive tree multigrid technique are then reviewed. The usefulness of the new MultiTrans code has been indicated by verifying and validating the code performance for different types of neutral and charged particle transport problems, reported in separate publications.

Radiation effects in supported nanoparticles

Nanotechnology applications are entering the market in increasing numbers, nanoparticles being among the main classes of materials used. Particles can be used, e.g., for catalysing chemical reactions, such as is done in car exhaust catalysts today. They can also modify the optical and electronic properties of materials or be used as building blocks for thin film coatings on a variety of surfaces. To develop materials for specific applications, an intricate control of the particle properties, structure, size and shape is required. All these depend on a multitude of factors from methods of synthesis and deposition to post-processing. This thesis addresses the control of nanoparticle structure by low-energy cluster beam deposition and post-synthesis ion irradiation. Cluster deposition in high vacuum offers a method for obtaining precisely controlled cluster-assembled materials with minimal contamination. Due to the clusters small size, however, the cluster-surface interaction may drastically change the cluster properties on deposition. In this thesis, the deposition process of metal and alloy clusters on metallic surfaces is modelled using molecular dynamics simulations, and the mechanisms influencing cluster structure are identified. Two mechanisms, mechanical melting upon deposition and thermally activated dislocation motion, are shown to determine whether a deposited cluster will align epitaxially with its support. The semiconductor industry has used ion irradiation as a tool to modify material properties for decades. Irradiation can be used for doping, patterning surfaces, and inducing chemical ordering in alloys, just to give a few examples. The irradiation response of nanoparticles has, however, remained an almost uncharted territory. Although irradiation effects in nanoparticles embedded inside solid matrices have been studied, almost no work has been done on supported particles. In this thesis, the response of supported nanoparticles is studied systematically for heavy and light ion irradiation. The processes leading to damage production are identified and models are developed for both types of irradiation. In recent experiments, helium irradiation has been shown to induce a phase transformation from multiply twinned to single-crystalline nanoparticles in bimetallic alloys, but the nature of the transition has remained unknown. The alloys for which the effect has been observed are CuAu and FePt. It is shown in this thesis that transient amorphization leads to the observed transition and that while CuAu and FePt do not amorphize upon irradiation in bulk or as thin films, they readily do so as nanoparticles. This is the first time such an effect is demonstrated with supported particles, not embedded in a matrix where mixing is always an issue. An understanding of the above physical processes is essential, if nanoparticles are to be used in applications in an optimal way. This thesis clarifies the mechanisms which control particle morphology, and paves way for the synthesis of nanostructured materials tailored for specific applications.

An agent based adaptive bandwidth allocation scheme for multimedia applications

Bandwidth allocation for multimedia applications in case of network congestion and failure poses technical challenges due to bursty and delay sensitive nature of the applications. The growth of multimedia services on Internet and the development of agent technology have made us to investigate new techniques for resolving the bandwidth issues in multimedia communications. Agent technology is emerging as a flexible promising solution for network resource management and QoS (Quality of Service) control in a distributed environment. In this paper, we propose an adaptive bandwidth allocation scheme for multimedia applications by deploying the static and mobile agents. It is a run-time allocation scheme that functions at the network nodes. This technique adaptively finds an alternate patchup route for every congested/failed link and reallocates the bandwidth for the affected multimedia applications. The designed method has been tested (analytical and simulation)with various network sizes and conditions. The results are presented to assess the performance and effectiveness of the approach. This work also demonstrates some of the benefits of the agent based schemes in providing flexibility, adaptability, software reusability, and maintainability. (C) 2004 Elsevier Inc. All rights reserved.

Hybrid learning scheme for data mining applications

Classification of large datasets is a challenging task in Data Mining. In the current work, we propose a novel method that compresses the data and classifies the test data directly in its compressed form. The work forms a hybrid learning approach integrating the activities of data abstraction, frequent item generation, compression, classification and use of rough sets.

Hybrid learning scheme for data mining applications

Classification of large datasets is a challenging task in Data Mining. In the current work, we propose a novel method that compresses the data and classifies the test data directly in its compressed form. The work forms a hybrid learning approach integrating the activities of data abstraction, frequent item generation, compression, classification and use of rough sets.

Suitability of a point-contact SAW-based stiffness transducer for biomedical applications

Methods of diagnosis in Biomedical applications can be broadly divided into contact and non-contact based methods. So far, ultrasound based methods have been found to be most favorable for non-contact, non-invasive diagnosis, especially in the case of tissue stiffness analysis. We report here, the fabrication and characterization details of a new contact based transducer system for qualitative determination of the stiffnesses of non-piezoelectric substrates using the phenomenon of Surface Acoustic Waves (SAW). Preliminary trials to study the functionality of this system were carried out on various metallic and non-metallic substrates, and the results were found to be satisfactory. To confirm the suitability of this system for biomedical applications, similar trials have been conducted on tissue mimicking phantoms with varying degrees of stiffness.

Studies on Binary Time Series Models with Applications to Empirical Macroeconomics and Finance

This thesis studies binary time series models and their applications in empirical macroeconomics and finance. In addition to previously suggested models, new dynamic extensions are proposed to the static probit model commonly used in the previous literature. In particular, we are interested in probit models with an autoregressive model structure. In Chapter 2, the main objective is to compare the predictive performance of the static and dynamic probit models in forecasting the U.S. and German business cycle recession periods. Financial variables, such as interest rates and stock market returns, are used as predictive variables. The empirical results suggest that the recession periods are predictable and dynamic probit models, especially models with the autoregressive structure, outperform the static model. Chapter 3 proposes a Lagrange Multiplier (LM) test for the usefulness of the autoregressive structure of the probit model. The finite sample properties of the LM test are considered with simulation experiments. Results indicate that the two alternative LM test statistics have reasonable size and power in large samples. In small samples, a parametric bootstrap method is suggested to obtain approximately correct size. In Chapter 4, the predictive power of dynamic probit models in predicting the direction of stock market returns are examined. The novel idea is to use recession forecast (see Chapter 2) as a predictor of the stock return sign. The evidence suggests that the signs of the U.S. excess stock returns over the risk-free return are predictable both in and out of sample. The new "error correction" probit model yields the best forecasts and it also outperforms other predictive models, such as ARMAX models, in terms of statistical and economic goodness-of-fit measures. Chapter 5 generalizes the analysis of univariate models considered in Chapters 2 4 to the case of a bivariate model. A new bivariate autoregressive probit model is applied to predict the current state of the U.S. business cycle and growth rate cycle periods. Evidence of predictability of both cycle indicators is obtained and the bivariate model is found to outperform the univariate models in terms of predictive power.