Algorithms for Maximum Independent Set in Convex Bipartite Graphs

A bipartite graph G = (V, W, E) is convex if there exists an ordering of the vertices of W such that, for each v. V, the neighbors of v are consecutive in W. We describe both a sequential and a BSP/CGM algorithm to find a maximum independent set in a convex bipartite graph. The sequential algorithm improves over the running time of the previously known algorithm and the BSP/CGM algorithm is a parallel version of the sequential one. The complexity of the algorithms does not depend on |W|.

Automatic camera control in virtual environments augmented using multiple sparse videos

Automated virtual camera control has been widely used in animation and interactive virtual environments. We have developed a multiple sparse camera based free view video system prototype that allows users to control the position and orientation of a virtual camera, enabling the observation of a real scene in three dimensions (3D) from any desired viewpoint. Automatic camera control can be activated to follow selected objects by the user. Our method combines a simple geometric model of the scene composed of planes (virtual environment), augmented with visual information from the cameras and pre-computed tracking information of moving targets to generate novel perspective corrected 3D views of the virtual camera and moving objects. To achieve real-time rendering performance, view-dependent textured mapped billboards are used to render the moving objects at their correct locations and foreground masks are used to remove the moving objects from the projected video streams. The current prototype runs on a PC with a common graphics card and can generate virtual 2D views from three cameras of resolution 768 x 576 with several moving objects at about 11 fps. (C)2011 Elsevier Ltd. All rights reserved.

Newton`s iterates can converge to non-stationary points

In this note we discuss the convergence of Newton`s method for minimization. We present examples in which the Newton iterates satisfy the Wolfe conditions and the Hessian is positive definite at each step and yet the iterates converge to a non-stationary point. These examples answer a question posed by Fletcher in his 1987 book Practical methods of optimization.

Improving ultimate convergence of an augmented Lagrangian method

Optimization methods that employ the classical Powell-Hestenes-Rockafellar augmented Lagrangian are useful tools for solving nonlinear programming problems. Their reputation decreased in the last 10 years due to the comparative success of interior-point Newtonian algorithms, which are asymptotically faster. In this research, a combination of both approaches is evaluated. The idea is to produce a competitive method, being more robust and efficient than its `pure` counterparts for critical problems. Moreover, an additional hybrid algorithm is defined, in which the interior-point method is replaced by the Newtonian resolution of a Karush-Kuhn-Tucker (KKT) system identified by the augmented Lagrangian algorithm. The software used in this work is freely available through the Tango Project web page:http://www.ime.usp.br/similar to egbirgin/tango/.

Augmented Lagrangian methods under the constant positive linear dependence constraint qualification

Two Augmented Lagrangian algorithms for solving KKT systems are introduced. The algorithms differ in the way in which penalty parameters are updated. Possibly infeasible accumulation points are characterized. It is proved that feasible limit points that satisfy the Constant Positive Linear Dependence constraint qualification are KKT solutions. Boundedness of the penalty parameters is proved under suitable assumptions. Numerical experiments are presented.

Reliability Nonparametric Bayesian Estimation in Parallel Systems

Relevant results for (sub-)distribution functions related to parallel systems are discussed. The reverse hazard rate is defined using the product integral. Consequently, the restriction of absolute continuity for the involved distributions can be relaxed. The only restriction is that the sets of discontinuity points of the parallel distributions have to be disjointed. Nonparametric Bayesian estimators of all survival (sub-)distribution functions are derived. Dual to the series systems that use minimum life times as observations, the parallel systems record the maximum life times. Dirichlet multivariate processes forming a class of prior distributions are considered for the nonparametric Bayesian estimation of the component distribution functions, and the system reliability. For illustration, two striking numerical examples are presented.

Bifurcation analysis of a model for biological control

In this paper we study the Lyapunov stability and Hopf bifurcation in a biological system which models the biological control of parasites of orange plantations. (c) 2007 Elsevier Ltd. All rights reserved.

Symmetry breaking in the genetic code: Finite groups

We investigate the possibility of interpreting the degeneracy of the genetic code, i.e., the feature that different codons (base triplets) of DNA are transcribed into the same amino acid, as the result of a symmetry breaking process, in the context of finite groups. In the first part of this paper, we give the complete list of all codon representations (64-dimensional irreducible representations) of simple finite groups and their satellites (central extensions and extensions by outer automorphisms). In the second part, we analyze the branching rules for the codon representations found in the first part by computational methods, using a software package for computational group theory. The final result is a complete classification of the possible schemes, based on finite simple groups, that reproduce the multiplet structure of the genetic code. (C) 2010 Elsevier Ltd. All rights reserved.

Asymmetric Ramsey Properties of Random Graphs Involving Cliques

Consider the following problem: Forgiven graphs G and F(1),..., F(k), find a coloring of the edges of G with k colors such that G does not contain F; in color i. Rodl and Rucinski studied this problem for the random graph G,,, in the symmetric case when k is fixed and F(1) = ... = F(k) = F. They proved that such a coloring exists asymptotically almost surely (a.a.s.) provided that p <= bn(-beta) for some constants b = b(F,k) and beta = beta(F). This result is essentially best possible because for p >= Bn(-beta), where B = B(F, k) is a large constant, such an edge-coloring does not exist. Kohayakawa and Kreuter conjectured a threshold function n(-beta(F1,..., Fk)) for arbitrary F(1), ..., F(k). In this article we address the case when F(1),..., F(k) are cliques of different sizes and propose an algorithm that a.a.s. finds a valid k-edge-coloring of G(n,p) with p <= bn(-beta) for some constant b = b(F(1),..., F(k)), where beta = beta(F(1),..., F(k)) as conjectured. With a few exceptions, this algorithm also works in the general symmetric case. We also show that there exists a constant B = B(F,,..., Fk) such that for p >= Bn(-beta) the random graph G(n,p) a.a.s. does not have a valid k-edge-coloring provided the so-called KLR-conjecture holds. (C) 2008 Wiley Periodicals, Inc. Random Struct. Alg., 34, 419-453, 2009

Flexibility and inhibitor binding in Cdc25 phosphatases

Cdc25 phosphatases involved in cell cycle checkpoints are now active targets for the development of anti-cancer therapies. Rational drug design would certainly benefit from detailed structural information for Cdc25s. However, only apo- or sulfate-bound crystal structures of the Cdc25 catalytic domain have been described so far. Together with previously available crystalographic data, results from molecular dynamics simulations, bioinformatic analysis, and computer-generated conformational ensembles shown here indicate that the last 30-40 residues in the C-terminus of Cdc25B are partially unfolded or disordered in solution. The effect of C-terminal flexibility upon binding of two potent small molecule inhibitors to Cdc25B is then analyzed by using three structural models with variable levels of flexibility, including an equilibrium distributed ensemble of Cdc25B backbone conformations. The three Cdc25B structural models are used in combination with flexible docking, clustering, and calculation of binding free energies by the linear interaction energy approximation to construct and validate Cdc25B-inhibitor complexes. Two binding sites are identified on top and beside the Cdc25B active site. The diversity of interaction modes found increases with receptor flexibility. Backbone flexibility allows the formation of transient cavities or compact hydrophobic units on the surface of the stable, folded protein core that are unexposed or unavailable for ligand binding in rigid and densely packed crystal structures. The present results may help to speculate on the mechanisms of small molecule complexation to partially unfolded or locally disordered proteins.

Effect of SO(2) on the Transport Properties of an Imidazolium Ionic Liquid and Its Lithium Solution

Transport coefficients have been measured as a function of the concentration of sulfur dioxide, SO(2), dissolved in 1-butyl-2,3-dimethylimidazolium bis(trifluoromethylsulfonyl)-imide, [BMMI][Tf(2)N], as well as in its lithium salt solution, Li[Tf(2)N]. The SO(2) reduces viscosity and density and increases conductivity and diffusion coefficients in both the neat [BMMI] [Tf(2)N] and the [BMMI][Tf(2)N]-Li[Tf(2)N] solution. The conductivity enhancement is not assigned to a simple viscosity effect; the weakening of ionic interactions upon SO(2) addition also plays a role. Microscopic details of the SO(2) effect were unraveled using Raman spectroscopy and molecular dynamics (MD) simulations. The Raman spectra suggest that the Li(+)-[Tf(2)N] interaction is barely affected by SO(2), and the SO(2)-[Tf(2)N] interaction is weaker than previously observed in an investigation of an ionic liquid containing the bromide anion. Transport coefficients calculated by MD simulations show the same trend as the experimental data with respect to SO(2) content. The MD simulations provide structural information on SO(2) molecules around [Tf(2)N], in particular the interaction of the sulfur atom of SO(2) with oxygen and fluorine atoms of the anion. The SO(2)-[BMMI] interaction is also important because the [BMMI] cations with above-average mobility have a larger number of nearest-neighbor SO(2) molecules.

Alkoxy Chain Effect on the Viscosity of a Quaternary Ammonium Ionic Liquid: Molecular Dynamics Simulations

The viscosity of ionic liquids based on quaternary ammonium cations is reduced when one of the alkyl chains is replaced by an alkoxy chain (Zhou et al. Chem. Eur. J. 2005, 11, 752.). A microscopic picture of the role played by the ether function in decreasing the viscosity of quaternary ammonium ionic liquids is provided here by molecular dynamics (MD) simulations. A model for the ionic liquid N-ethyl-N,N-dimethyl-N-(2-methoxyethyl)ammonium bis(trifluoromethanesulfonyl)imide, MOENM(2)E TFSI, is compared to the tetraalky-lammonium counterpart. The alkoxy derivative has lower viscosity, higher ionic diffusion coefficients, and higher conductivity than the tetraalkyl system at the same density and temperature. A clear signature of the ether function on the liquid structure is observed in cation-cation correlations, but not in anion-anion or anion-cation correlations. In both the alkyl and the alkoxy ionic liquids, there is aggregation of long chains of neighboring cations within micelle-like structures. The MD simulations indicate that the less effective assembly between the more flexible alkoxy chains, in comparison to alkyl chains, is the structural reason for higher ionic mobility in MOENM(2)E TFSI.

Shielding of ionic interactions by sulfur dioxide in an ionic liquid

The effect of adding SO(2) on the structure and dynamics of 1-butyl-3-methylimidazolium bromide (BMIBr) was investigated by low-frequency Raman spectroscopy and molecular dynamics (MD) simulations. The MD simulations indicate that the long-range structure of neat BMIBr is disrupted resulting in a liquid with relatively low viscosity and high conductivity, but strong correlation of ionic motion persists in the BMIBr-SO(2) mixture due to ionic pairing. Raman spectra within the 5 < omega < 200 cm(-1) range at low temperature reveal the short-time dynamics, which is consistent with the vibrational density of states calculated by MD simulations. Several time correlation functions calculated by MD simulations give further insights on the structural relaxation of BMIBr-SO(2).

Developing a Communication link between Agents and cross Platform IDE

The main objective of this thesis work is to develop communication link between Runrev Revolution (IDE) and JADE (Multi-Agent System) through Socket programming using TCP/IP layer. These two independent platforms are connected using socket programming technique. Socket programming is considered to be newly emerging technology among these two platforms, the work done in this thesis work is considered to be a prototype.A Graphical simulation model is developed by salixphere (Company in Hedemora) to simulate logistic problems using Runrev Revolution (IDE). The simulation software/program is called “BIOSIM”. The logistic problems are complex, and conventional optimization techniques are unlikely very successful. “BIOSIM” can demonstrate the graphical representation of logistic problems depending upon the problem domains. As this simulation model is developed in revolution programming language (Transcript) which is dynamically typed and English-like language, it is quite slow compared to other high level programming languages. The object of this thesis work is to add intelligent behaviour in graphical objects and develop communication link between Runrev revolution (IDE) and JADE (Multi-Agent System) using TCP/IP layers.The test shows the intelligent behaviour in the graphical objects and successful communication between Runrev Revolution (IDE) and JADE (Multi-Agent System).

Separation and Execution of graphical engine on a cross platform IDE to enhance performance

“Biosim” is a simulation software which works to simulate the harvesting system.This system is able to design a model for any logistic problem with the combination of several objects so that the artificial system can show the performance of an individual model. The system will also describe the efficiency, possibility to be chosen for real life application of that particular model. So, when any one wish to setup a logistic model like- harvesting system, in real life he/she may be noticed about the suitable prostitution for his plants and factories as well as he/she may get information about the least number of objects, total time to complete the task, total investment required for his model, total amount of noise produced for his establishment in advance. It will produce an advance over view for his model. But “Biosim” is quite slow .As it is an object based system, it takes long time to make its decision. Here the main task is to modify the system so that it can work faster than the previous. So, the main objective of this thesis is to reduce the load of “Biosim” by making some modification of the original system as well as to increase its efficiency. So that the whole system will be faster than the previous one and performs more efficiently when it will be applied in real life. Theconcept is to separate the execution part of ”Biosim” form its graphical engine and run this separated portion in a third generation language platform. C++ is chosenhere as this external platform. After completing the proposed system, results with different models have been observed. The results show that, for any type of plants of fields, for any number of trucks, the proposed system is faster than the original system. The proposed system takes at least 15% less time “Biosim”. The efficiency increase with the complexity of than the original the model. More complex the model, more efficient the proposed system is than original “Biosim”.Depending on the complexity of a model, the proposed system can be 56.53 % faster than the original “Biosim”.