Fast edge splitting and Edmonds' arborescence construction for unweighted graphs

Given an unweighted undirected or directed graph with n vertices, m edges and edge connectivity c, we present a new deterministic algorithm for edge splitting. Our algorithm splits-off any specified subset S of vertices satisfying standard conditions (even degree for the undirected case and in-degree ≥ out-degree for the directed case) while maintaining connectivity c for vertices outside S in Õ(m+nc2) time for an undirected graph and Õ(mc) time for a directed graph. This improves the current best deterministic time bounds due to Gabow [8], who splits-off a single vertex in Õ(nc2+m) time for an undirected graph and Õ(mc) time for a directed graph. Further, for appropriate ranges of n, c, |S| it improves the current best randomized bounds due to Benczúr and Karger [2], who split-off a single vertex in an undirected graph in Õ(n2) Monte Carlo time. We give two applications of our edge splitting algorithms. Our first application is a sub-quadratic (in n) algorithm to construct Edmonds' arborescences. A classical result of Edmonds [5] shows that an unweighted directed graph with c edge-disjoint paths from any particular vertex r to every other vertex has exactly c edge-disjoint arborescences rooted at r. For a c edge connected unweighted undirected graph, the same theorem holds on the digraph obtained by replacing each undirected edge by two directed edges, one in each direction. The current fastest construction of these arborescences by Gabow [7] takes Õ(n2c2) time. Our algorithm takes Õ(nc3+m) time for the undirected case and Õ(nc4+mc) time for the directed case. The second application of our splitting algorithm is a new Steiner edge connectivity algorithm for undirected graphs which matches the best known bound of Õ(nc2 + m) time due to Bhalgat et al [3]. Finally, our algorithm can also be viewed as an alternative proof for existential edge splitting theorems due to Lovász [9] and Mader [11].

An operator-splitting finite element method for the efficient parallel solution of multidimensional population balance systems

A finite element method for solving multidimensional population balance systems is proposed where the balance of fluid velocity, temperature and solute partial density is considered as a two-dimensional system and the balance of particle size distribution as a three-dimensional one. The method is based on a dimensional splitting into physical space and internal property variables. In addition, the operator splitting allows to decouple the equations for temperature, solute partial density and particle size distribution. Further, a nodal point based parallel finite element algorithm for multi-dimensional population balance systems is presented. The method is applied to study a crystallization process assuming, for simplicity, a size independent growth rate and neglecting agglomeration and breakage of particles. Simulations for different wall temperatures are performed to show the effect of cooling on the crystal growth. Although the method is described in detail only for the case of d=2 space and s=1 internal property variables it has the potential to be extendable to d+s variables, d=2, 3 and s >= 1. (C) 2011 Elsevier Ltd. All rights reserved.

Phase separation by nanoparticle splitting

The present report illustrates the phenomenon of phase separation leading to the splitting of solid solution structured Ag-Co nanoparticles into pure Ag and pure Co nanoparticles upon isothermal annealing inside a transmission electron microscope. In bulk, Ag-Co system shows negligible mutual solubility into a single phase solid solution structure upto a very high temperature. The Ag-Co nanoparticle splitting revealed that room temperature, solid solution atomic configuration, between bulk immiscible Ag and Co atoms coexisting in a nano-sized particle, is a kinetically frozen atomic arrangement and not a thermodynamically stable structure. The observed phase separation behavior resulting in particle splitting at high temperatures can be used to produce devices for sensor applications. (C) 2011 Elsevier B.V. All rights reserved.

An operator-splitting Galerkin/SUPG finite element method for population balance equations : stability and convergence

We present a heterogeneous finite element method for the solution of a high-dimensional population balance equation, which depends both the physical and the internal property coordinates. The proposed scheme tackles the two main difficulties in the finite element solution of population balance equation: (i) spatial discretization with the standard finite elements, when the dimension of the equation is more than three, (ii) spurious oscillations in the solution induced by standard Galerkin approximation due to pure advection in the internal property coordinates. The key idea is to split the high-dimensional population balance equation into two low-dimensional equations, and discretize the low-dimensional equations separately. In the proposed splitting scheme, the shape of the physical domain can be arbitrary, and different discretizations can be applied to the low-dimensional equations. In particular, we discretize the physical and internal spaces with the standard Galerkin and Streamline Upwind Petrov Galerkin (SUPG) finite elements, respectively. The stability and error estimates of the Galerkin/SUPG finite element discretization of the population balance equation are derived. It is shown that a slightly more regularity, i.e. the mixed partial derivatives of the solution has to be bounded, is necessary for the optimal order of convergence. Numerical results are presented to support the analysis.

Operator-splitting finite element algorithms for computations of high-dimensional parabolic problems

An operator-splitting finite element method for solving high-dimensional parabolic equations is presented. The stability and the error estimates are derived for the proposed numerical scheme. Furthermore, two variants of fully-practical operator-splitting finite element algorithms based on the quadrature points and the nodal points, respectively, are presented. Both the quadrature and the nodal point based operator-splitting algorithms are validated using a three-dimensional (3D) test problem. The numerical results obtained with the full 3D computations and the operator-split 2D + 1D computations are found to be in a good agreement with the analytical solution. Further, the optimal order of convergence is obtained in both variants of the operator-splitting algorithms. (C) 2012 Elsevier Inc. All rights reserved.

Microstructure and texture evolution during sub-transus thermo-mechanical processing of Ti-6Al-4V-0.1B alloy: part II. static annealing in (alpha plus beta) regime

The first part of this study describes the evolution of microstructure and texture in Ti-6Al-4V-0.1B alloy during sub-transus rolling vis-A -vis the control alloy Ti-6Al-4V. In the second part, the static annealing response of the two alloys at self-same conditions is compared and the principal micromechanisms are analyzed. Faster globularization kinetics has been observed in the Ti-6Al-4V-0.1B alloy for equivalent annealing conditions. This is primarily attributed to the alpha colonies, which leads to easy boundary splitting via multiple slip activation in this alloy. The other mechanisms facilitating lamellar to equiaxed morphological transformations, e.g., termination migration and cylinderization, also start early in the boron-modified alloy due to small alpha colony size, small aspect ratio of the alpha lamellae, and the presence of TiB particles in the microstructure. Both the alloys exhibit weakening of basal fiber (ND||aOE (c) 0001 >) and strengthening of prism fiber (RD||aOE (c) aOE(a)) upon annealing. A close proximity between the orientations of fully globularized primary alpha and secondary alpha phases during alpha -> beta -> alpha transformation has accounted for such a texture modification.

Capture-Induced, Fast, Distributed, Splitting Based Selection with Imperfect Power Control

Opportunistic selection selects the node that improves the overall system performance the most. Selecting the best node is challenging as the nodes are geographically distributed and have only local knowledge. Yet, selection must be fast to allow more time to be spent on data transmission, which exploits the selected node's services. We analyze the impact of imperfect power control on a fast, distributed, splitting based selection scheme that exploits the capture effect by allowing the transmitting nodes to have different target receive powers and uses information about the total received power to speed up selection. Imperfect power control makes the received power deviate from the target and, hence, affects performance. Our analysis quantifies how it changes the selection probability, reduces the selection speed, and leads to the selection of no node or a wrong node. We show that the effect of imperfect power control is primarily driven by the ratio of target receive powers. Furthermore, we quantify its effect on the net system throughput.

Artificial photosynthesis and the splitting of water to generate hydrogen

It is no exaggeration to state that the energy crisis is the most serious challenge that we face today. Among the strategies to gain access to reliable, renewable energy, the use of solar energy has clearly emerged as the most viable option. A promising direction in this context is artificial photosynthesis. In this article, we briefly describe the essential features of artificial photosynthesis in comparison with natural photosynthesis and point out the modest success that we have had in splitting water to produce oxygen and hydrogen, specially the latter.

Anisotropic merging and splitting of dipolar Bose-Einstein condensates

We study the merging and splitting of quasi-two-dimensional Bose-Einstein condensates with strong dipolar interactions. We observe that if the dipoles have a non-zero component in the plane of the condensate, the dynamics of merging or splitting along two orthogonal directions, parallel and perpendicular to the projection of dipoles on the plane of the condensate, are different. The anisotropic merging and splitting of the condensate is a manifestation of the anisotropy of the roton-like mode in the dipolar system. The difference in dynamics disappears if the dipoles are oriented at right angles to the plane of the condensate as in this case the Bogoliubov dispersion, despite having roton-like features, is isotropic.

Social insect colony as a biological regulatory system: modelling information flow in dominance networks

Social insects provide an excellent platform to investigate flow of information in regulatory systems since their successful social organization is essentially achieved by effective information transfer through complex connectivity patterns among the colony members. Network representation of such behavioural interactions offers a powerful tool for structural as well as dynamical analysis of the underlying regulatory systems. In this paper, we focus on the dominance interaction networks in the tropical social wasp Ropalidia marginata-a species where behavioural observations indicate that such interactions are principally responsible for the transfer of information between individuals about their colony needs, resulting in a regulation of their own activities. Our research reveals that the dominance networks of R. marginata are structurally similar to a class of naturally evolved information processing networks, a fact confirmed also by the predominance of a specific substructure-the `feed-forward loop'-a key functional component in many other information transfer networks. The dynamical analysis through Boolean modelling confirms that the networks are sufficiently stable under small fluctuations and yet capable of more efficient information transfer compared to their randomized counterparts. Our results suggest the involvement of a common structural design principle in different biological regulatory systems and a possible similarity with respect to the effect of selection on the organization levels of such systems. The findings are also consistent with the hypothesis that dominance behaviour has been shaped by natural selection to co-opt the information transfer process in such social insect species, in addition to its primal function of mediation of reproductive competition in the colony.