Efficient Algorithms for Computing All Low s-t Edge Connectivities and Related Problems

Given an undirected unweighted graph G = (V, E) and an integer k ≥ 1, we consider the problem of computing the edge connectivities of all those (s, t) vertex pairs, whose edge connectivity is at most k. We present an algorithm with expected running time Õ(m + nk3) for this problem, where |V| = n and |E| = m. Our output is a weighted tree T whose nodes are the sets V1, V2,..., V l of a partition of V, with the property that the edge connectivity in G between any two vertices s ε Vi and t ε Vj, for i ≠ j, is equal to the weight of the lightest edge on the path between Vi and Vj in T. Also, two vertices s and t belong to the same Vi for any i if and only if they have an edge connectivity greater than k. Currently, the best algorithm for this problem needs to compute all-pairs min-cuts in an O(nk) edge graph; this takes Õ(m + n5/2kmin{k1/2, n1/6}) time. Our algorithm is much faster for small values of k; in fact, it is faster whenever k is o(n5/6). Our algorithm yields the useful corollary that in Õ(m + nc3) time, where c is the size of the global min-cut, we can compute the edge connectivities of all those pairs of vertices whose edge connectivity is at most αc for some constant α. We also present an Õ(m + n) Monte Carlo algorithm for the approximate version of this problem. This algorithm is applicable to weighted graphs as well. Our algorithm, with some modifications, also solves another problem called the minimum T-cut problem. Given T ⊆ V of even cardinality, we present an Õ(m + nk3) algorithm to compute a minimum cut that splits T into two odd cardinality components, where k is the size of this cut.

Convergence problems in a class of model reference adaptive control systems

A class of model reference adaptive control system which make use of an augmented error signal has been introduced by Monopoli. Convergence problems in this attractive class of systems have been investigated in this paper using concepts from hyperstability theory. It is shown that the condition on the linear part of the system has to be stronger than the one given earlier. A boundedness condition on the input to the linear part of the system has been taken into account in the analysis - this condition appears to have been missed in the previous applications of hyperstability theory. Sufficient conditions for the convergence of the adaptive gain to the desired value are also given.

Scattering theory and linear optimal control: Regulator and servo problems

In this paper, several known computational solutions are readily obtained in a very natural way for the linear regulator, fixed end-point and servo-mechanism problems using a certain frame-work from scattering theory. The relationships between the solutions to the linear regulator problem with different terminal costs and the interplay between the forward and backward equations have enabled a concise derivation of the partitioned equations, the forward-backward equations, and Chandrasekhar equations for the problem. These methods have been extended to the fixed end-point, servo, and tracking problems.

Phase-plane techniques for the solution of transient-stability problems

The paper presents a graphical-numerical method for determining the transient stability limits of a two-machine system under the usual assumptions of constant input, no damping and constant voltage behind transient reactance. The method presented is based on the phase-plane criterion,1, 2 in contrast to the usual step-by-step and equal-area methods. For the transient stability limit of a two-machine system, under the assumptions stated, the sum of the kinetic energy and the potential energy, at the instant of fault clearing, should just be equal to the maximum value of the potential energy which the machines can accommodate with the fault cleared. The assumption of constant voltage behind transient reactance is then discarded in favour of the more accurate assumption of constant field flux linkages. Finally, the method is extended to include the effect of field decrement and damping. A number of examples corresponding to each case are worked out, and the results obtained by the proposed method are compared with those obtained by the usual methods.

Homogenization of eigenvalue problems in perforated domains

In this paper, we treat some eigenvalue problems in periodically perforated domains and study the asymptotic behaviour of the eigenvalues and the eigenvectors when the number of holes in the domain increases to infinity Using the method of asymptotic expansion, we give explicit formula for the homogenized coefficients and expansion for eigenvalues and eigenvectors. If we denote by ε the size of each hole in the domain, then we obtain the following aysmptotic expansion for the eigenvalues: Dirichlet: λε = ε−2 λ + λ0 +O (ε), Stekloff: λε = ελ1 +O (ε2), Neumann: λε = λ0 + ελ1 +O (ε2).Using the method of energy, we prove a theorem of convergence in each case considered here. We briefly study correctors in the case of Neumann eigenvalue problem.

Mechanism design problems in carbon economics

Reduction of carbon emissions is of paramount importance in the context of global warming and climate change. Countries and global companies are now engaged in understanding systematic ways of solving carbon economics problems, aimed ultimately at achieving well defined emission targets. This paper proposes mechanism design as an approach to solving carbon economics problems. The paper first introduces carbon economics issues in the world today and next focuses on carbon economics problems facing global industries. The paper identifies four problems faced by global industries: carbon credit allocation (CCA), carbon credit buying (CCB), carbon credit selling (CCS), and carbon credit exchange (CCE). It is argued that these problems are best addressed as mechanism design problems. The discipline of mechanism design is founded on game theory and is concerned with settings where a social planner faces the problem of aggregating the announced preferences of multiple agents into a collective decision, when the actual preferences are not known publicly. The paper provides an overview of mechanism design and presents the challenges involved in designing mechanisms with desirable properties. To illustrate the application of mechanism design in carbon economics,the paper describes in detail one specific problem, the carbon credit allocation problem.

Two-dimensional approximations of 3-dimensional eigenvalue problems in plate-theory

The eigenvalues and eigenfunctions corresponding to the three-dimensional equations for the linear elastic equilibrium of a clamped plate of thickness 2ϵ, are shown to converge (in a specific sense) to the eigenvalues and eigenfunctions of the well-known two-dimensional biharmonic operator of plate theory, as ϵ approaches zero. In the process, it is found in particular that the displacements and stresses are indeed of the specific forms usually assumed a priori in the literature. It is also shown that the limit eigenvalues and eigenfunctions can be equivalently characterized as the leading terms in an asymptotic expansion of the three-dimensional solutions, in terms of powers of ϵ. The method presented here applies equally well to the stationary problem of linear plate theory, as shown elsewhere by P. Destuynder.

Smooth DMS-FEM: A new approach to solving nearly incompressible nonlinear elasto-static problems

The DMS-FEM, which enables functional approximations with C(1) or still higher inter-element continuity within an FEM-based meshing of the domain, has recently been proposed by Sunilkumar and Roy [39,40]. Through numerical explorations on linear elasto-static problems, the method was found to have conspicuously superior convergence characteristics as well as higher numerical stability against locking. These observations motivate the present study, which aims at extending and exploring the DMS-FEM to (geometrically) nonlinear elasto-static problems of interest in solid mechanics and assessing its numerical performance vis-a-vis the FEM. In particular, the DMS-FEM is shown to vastly outperform the FEM (presently implemented through the commercial software ANSYS (R)) as the former requires fewer linearization and load steps to achieve convergence. In addition, in the context of nearly incompressible nonlinear systems prone to volumetric locking and with no special numerical artefacts (e.g. stabilized or mixed weak forms) employed to arrest locking, the DMS-FEM is shown to approach the incompressibility limit much more closely and with significantly fewer iterations than the FEM. The numerical findings are suggestive of the important role that higher order (uniform) continuity of the approximated field variables play in overcoming volumetric locking and the great promise that the method holds for a range of other numerically ill-conditioned problems of interest in computational structural mechanics. (C) 2011 Elsevier Ltd. All rights reserved.