Faster Algorithms for All-pairs Approximate Shortest Paths in Undirected Graphs

Let G - (V, E) be a weighted undirected graph having nonnegative edge weights. An estimate (delta) over cap (u, v) of the actual distance d( u, v) between u, v is an element of V is said to be of stretch t if and only if delta(u, v) <= (delta) over cap (u, v) <= t . delta(u, v). Computing all-pairs small stretch distances efficiently ( both in terms of time and space) is a well-studied problem in graph algorithms. We present a simple, novel, and generic scheme for all-pairs approximate shortest paths. Using this scheme and some new ideas and tools, we design faster algorithms for all-pairs t-stretch distances for a whole range of stretch t, and we also answer an open question posed by Thorup and Zwick in their seminal paper [J. ACM, 52 (2005), pp. 1-24].

The condensed nearest neighbor rule using the concept of mutual nearest neighborhood (Corresp.)

A two-stage iterative algorithm for selecting a subset of a training set of samples for use in a condensed nearest neighbor (CNN) decision rule is introduced. The proposed method uses the concept of mutual nearest neighborhood for selecting samples close to the decision line. The efficacy of the algorithm is brought out by means of an example.

Approximate VB-MO schemes for excitation gaps in Hubbard models

The excitation gaps in the singlet and triplet manifolds for finite Hubbard models in one, two and three dimensions have been obtained using different approximate configuration interaction (CI) schemes, as a function of the correlation strength, by using valence bond (VB) functions constructed over the molecular orbital (MO) basis. These are compared with numerically exact results and it is found that the scheme in which all particle hole excitations below a given threshold are included is the method of choice. The excitation energies are well reproduced, in trend as well as magnitude, particularly when the threshold equals the bandwidth of the corresponding noninteracting system.

NDDO-based CI methods for the prediction of electronic spectra and sum-over-states molecular hyperpolarization

NDDO-based (AM1) configuration interaction (CI) calculations have been used to calculate the wavelength and oscillator strengths of electronic absorptions in organic molecules and the results used in a sum-over-states treatment to calculate second-order-hyperpolarizabilities. The results for both spectra and hyperpolarizabilities are of acceptable quality as long as a suitable CI-expansion is used. We have found that using an active space of eight electrons in eight orbitals and including all single and pair-double excitations in the CI leads to results that agree well with experiment and that do not change significantly with increasing active space for most organic molecules. Calculated second-order hyperpolarizabilities using this type of CI within a sum-over-states calculation appear to be of useful accuracy.

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.

Robust/Optimal Temperature Profile Control of a High-Speed Aerospace Vehicle Using Neural Networks

An approximate dynamic programming (ADP)-based suboptimal neurocontroller to obtain desired temperature for a high-speed aerospace vehicle is synthesized in this paper. A I-D distributed parameter model of a fin is developed from basic thermal physics principles. "Snapshot" solutions of the dynamics are generated with a simple dynamic inversion-based feedback controller. Empirical basis functions are designed using the "proper orthogonal decomposition" (POD) technique and the snapshot solutions. A low-order nonlinear lumped parameter system to characterize the infinite dimensional system is obtained by carrying out a Galerkin projection. An ADP-based neurocontroller with a dual heuristic programming (DHP) formulation is obtained with a single-network-adaptive-critic (SNAC) controller for this approximate nonlinear model. Actual control in the original domain is calculated with the same POD basis functions through a reverse mapping. Further contribution of this paper includes development of an online robust neurocontroller to account for unmodeled dynamics and parametric uncertainties inherent in such a complex dynamic system. A neural network (NN) weight update rule that guarantees boundedness of the weights and relaxes the need for persistence of excitation (PE) condition is presented. Simulation studies show that in a fairly extensive but compact domain, any desired temperature profile can be achieved starting from any initial temperature profile. Therefore, the ADP and NN-based controllers appear to have the potential to become controller synthesis tools for nonlinear distributed parameter systems.

The approximate parametrization of the curve of intersection of implicit surfaces

A clear definition of an approximate parametrization of the curve of intersection of (n-1) implicit surfaces in Rn is given. It is justified that marching methods yield such an approximation.

Performance of the generalized delta rule in structural damage detection

The paper examines the suitability of the generalized data rule in training artificial neural networks (ANN) for damage identification in structures. Several multilayer perceptron architectures are investigated for a typical bridge truss structure with simulated damage stares generated randomly. The training samples have been generated in terms of measurable structural parameters (displacements and strains) at suitable selected locations in the structure. Issues related to the performance of the network with reference to hidden layers and hidden. neurons are examined. Some heuristics are proposed for the design of neural networks for damage identification in structures. These are further supported by an investigation conducted on five other bridge truss configurations.

Constant pressure laminar, transitional and turbulent flows - An approximate unified treatment

A nondimensional number that is constant in two-dimensional, incompressible and constant pressure laminar and fully turbulent boundary, layer flows has been proposed. An extension of this to constant pressure transitional flow is discussed.

Large eddy simulation of a premixed flame with approximate deconvolution modeling

Approximate deconvolution modeling is a very recent approach to large eddy simulation of turbulent flows. It has been applied to compressible flows with success. Here, a premixed flame which forms in the wake of a flameholder has been selected to examine the subgrid-scale modeling of reaction rate by this new method because a previous plane two-dimensional simulation of this wake flame, using a wrinkling function and artificial flame thickening, had revealed discrepancies when compared with experiment. The present simulation is of the temporal evolution of a round wakelike flow at two Reynolds numbers, Re = 2000 and 10,000, based on wake defect velocity and wake diameter. A Fourier-spectral code has been used. The reaction is single-step and irreversible, and the rate follows an Arrhenius law. The reference simulation at the lower Reynolds number is fully resolved. At Re = 10,000, subgrid-scale contributions are significant. It was found that subgrid-scale modeling in the present simulation agrees more closely with unresolved subgrid-scale effects observed in experiment. Specifically, the highest contributions appeared in thin folded regions created by vortex convection. The wrinkling function approach had not selected subgrid-scale effects in these regions.

Survival of the fittest and zero sum games

Competition for available resources is natural amongst coexisting species, and the fittest contenders dominate over the rest in evolution. The. dynamics of this selection is studied using a simple linear model. It has similarities to features of quantum computation, in particular conservation laws leading to destructive interference. Compared to an altruistic scenario, competition introduces instability and eliminates the weaker species in a finite time.

Rule-based modelling of iron homeostasis in tuberculosis

To establish itself within the host system, Mycobacterium tuberculosis (Mtb) has formulated various means of attacking the host system. One such crucial strategy is the exploitation of the iron resources of the host system. Obtaining and maintaining the required concentration of iron becomes a matter of contest between the host and the pathogen, both trying to achieve this through complex molecular networks. The extent of complexity makes it important to obtain a systems perspective of the interplay between the host and the pathogen with respect to iron homeostasis. We have reconstructed a systems model comprising 92 components and 85 protein-protein or protein-metabolite interactions, which have been captured as a set of 194 rules. Apart from the interactions, these rules also account for protein synthesis and decay, RBC circulation and bacterial production and death rates. We have used a rule-based modelling approach, Kappa, to simulate the system separately under infection and non-infection conditions. Various perturbations including knock-outs and dual perturbation were also carried out to monitor the behavioral change of important proteins and metabolites. From this, key components as well as the required controlling factors in the model that are critical for maintaining iron homeostasis were identified. The model is able to re-establish the importance of iron-dependent regulator (ideR) in Mtb and transferrin (Tf) in the host. Perturbations, where iron storage is increased, appear to enhance nutritional immunity and the analysis indicates how they can be harmful for the host. Instead, decreasing the rate of iron uptake by Tf may prove to be helpful. Simulation and perturbation studies help in identifying Tf as a possible drug target. Regulating the mycobactin (myB) concentration was also identified as a possible strategy to control bacterial growth. The simulations thus provide significant insight into iron homeostasis and also for identifying possible drug targets for tuberculosis.

Approximate synthesis formulas for microstrip line with aperture in ground plane

Approximate closed-form expressions for the propagation characteristics of a microstrip line with a symmetrical aperture in its ground plane are reported in this article. Well-known expressions for the characteristic impedance of a regular microstrip line have been modified to incorporate the effect of this aperture. The accuracy of these expressions for various values of substrate thickness, permittivity and line width has been studied in detail by fullwave simulations. This has been further verified by measurements. These expressions are easier to compute and find immense use in the design of broadband filters, tight couplers, power dividers, transformers, delay lines, and matching circuits. A broadband filter with aperture in ground plane is demonstrated in this article. (c) 2011 Wiley Periodicals, Inc. Int J RF and Microwave CAE, 2012.