A weak immersion relation on graphs and its applications

Weak immersion is a generalization of the immersion relation defined by Nash-Williams. A graph H is said to be weakly immersed in a graph G if H can be obtained from G by a sequence of these three operations: taking a subgraph, splitting a vertex, and lifting a pair of adjacent edges. The weak immersion relation has the useful property that finite graphs are well-quasi-ordered by it, which also holds for graphs with some vertices designated as terminals. As a result, any family of finite graphs that is closed under weak immersion can be characterized by a finite number of minimal forbidden graphs called obstructions. Weak immersion offers two advantages over immersion for practical applications. First, although closure under weak immersion implies closure under immersion, families can have significantly fewer obstructions under weak immersion. Hence weak immersion can provide simpler characterizations for closed families. Examples include graphs of bounded cutwidth and graphs of bounded multiway cutsize. The difference in the number of obstructions is at least exponential in the cutwidth and in the square-root of the multiway cutsize. Second, for every fixed graph H, there is a polynomial-time algorithm to decide whether H is weakly immersed in an input graph G. Consequently, there is a polynomial-time membership test for any family that is closed under weak immersion. In principle, testing for weak immersion is as fast as testing for immersion. Thus the simpler characterization provided by weak immersion may lead to faster membership algorithms.     

Parallel simulation of individual-based, physiologically structured population models

A general scheme for parallel simulation of individual-based, structured population models is proposed. Algorithms are developed to simulate such models in a parallel computing environment. The simulation model consists of an individual model and a population model that incorporates the individual dynamics. The individual model is a continuous time representation of organism life history for growth with discrete allocations for reproductive processes. The population model is a continuous time simulation of a nonlinear partial differential equation of extended McKendrick-von Foerster-type.

As a prototypical example, we show that a specific individual-based, physiologically structured model for Daphnia populations is well suited for parallelization, and significant speed-ups can be obtained by using efficient algorithms developed along our general scheme. Because the parallel algorithms are applicable to generic structured populations which are the foundation for populations in a more complex community or food-web model, parallel computation appears to be a valuable tool for ecological modeling and simulation.     

Inhibitory Effect of Biosynthesized Silver Nanoparticles from Extract of <Emphasis Type="Italic">Nitzschia palea</Emphasis> Against Curli-Mediated Biofilm of <Emphasis Type="Italic">Escherichia coli</Emphasis>

Extended spectrum beta lactamase (ESBL) are emerging beta-lactamases in Gram-negative pathogens, causing serious problems in hospitalized patients worldwide. Biofilm mode of virulence has decreased the efficiency of antibiotics used for treatment against ESBL pathogens. Therefore, there is an urgent need for alternative agents such as nanoparticles that can prevent and inhibit the biofilm formation. The aim of the present study was to inhibit the biofilm formed by ESBL-producing Escherichia coli using silver nanoparticles (AgNPs) synthesized with fresh water diatom (Nitzschia palea). AgNPs were characterized using UV-Vis spectroscopy, Fourier transform infrared (FTIR) spectroscopy, field emission scanning electron microscope (FESEM), energy-dispersive X-ray spectroscopy (EDX), and XRD. AgNPs at their biofilm inhibitory concentration (BIC) of 300 ng ml^?1 significantly reduced the biofilm formed by E. coli. Interestingly, Congo red assay revealed the reduction of curli, essential for biofilm formation in the presence of AgNPs. Light and CLSM examination of the biofilm images also validated that in the presence of AgNPs, the biofilm architecture was disintegrated and the thickness was significantly reduced. Overall, the present study exemplifies the use of AgNPs as a plausible alternative for conventional coating agents on implant devices to prevent and control biofilm-associated urinary tract infections.     

Fast Algorithms forK4Immersion Testing

Many useful classes of graphs can in principle be recognized with finite batteries of obstruction tests. One of the most fundamental tests is to determine whether an arbitrary input graph containsK₄in the immersion order. In this paper, we present for the first time a fast, practical algorithm to accomplish this task. We also extend our method so that, should an immersedK₄be present, aK₄model is isolated.