An (O)over-tilde(mn) Gomory-Hu Tree Construction Algorithm for Unweighted Graphs

We present a fast algorithm for computing a Gomory-Hu tree or cut tree for an unweighted undirected graph G = (V, E). The expected running time of our algorithm is (O) over tilde (mc) where vertical bar E vertical bar = m and c is the maximum u-v edge connectivity, where u, v is an element of V. When the input graph is also simple (i.e., it has no parallel edges), then the u-v edge connectivity for each pair of vertices u and v is at most n - 1; so the expected run-ning time of our algorithm for simple unweighted graphs is (O) over tilde (mn). All the algorithms currently known for constructing a Gomory-Hu tree [8, 9] use n - 1 minimum s-t cut (i.e., max flow) subroutines. This in conjunction with the current fastest (O) over tilde (n(20/9)) max flow algorithm due to Karger and Levine[11] yields the current best running time of (O) over tilde (n(20/9)n) for Gomory-Hu tree construction on simple unweighted graphs with m edges and n vertices. Thus we present the first (O) over tilde (mn) algorithm for constructing a Gomory-Hu tree for simple unweighted graphs. We do not use a max flow subroutine here; we present an efficient tree packing algorithm for computing Steiner edge connectivity and use this algorithm as our main subroutine. The advantage in using a tree packing algorithm for constructing a Gomory-Hu tree is that the work done in computing a minimum Steiner cut for a Steiner set S subset of V can be reused for computing a minimum Steiner cut for certain Steiner sets S' subset of S.

On the Arrangement of Cliques in Chordal Graphs with respect to the Cuts

A cut (A, B) (where B = V - A) in a graph G = (V, E) is called internal if and only if there exists a vertex x in A that is not adjacent to any vertex in B and there exists a vertex y is an element of B such that it is not adjacent to any vertex in A. In this paper, we present a theorem regarding the arrangement of cliques in a chordal graph with respect to its internal cuts. Our main result is that given any internal cut (A, B) in a chordal graph G, there exists a clique with kappa(G) + vertices (where kappa(G) is the vertex connectivity of G) such that it is (approximately) bisected by the cut (A, B). In fact we give a stronger result: For any internal cut (A, B) of a chordal graph, and for each i, 0 <= i <= kappa(G) + 1 such that vertical bar K-i vertical bar = kappa(G) + 1, vertical bar A boolean AND K-i vertical bar = i and vertical bar B boolean AND K-i vertical bar = kappa(G) + 1 - i. An immediate corollary of the above result is that the number of edges in any internal cut (of a chordal graph) should be Omega(k(2)), where kappa(G) = k. Prompted by this observation, we investigate the size of internal cuts in terms of the vertex connectivity of the chordal graphs. As a corollary, we show that in chordal graphs, if the edge connectivity is strictly less than the minimum degree, then the size of the mincut is at least kappa(G)(kappa(G)+1)/2 where kappa(G) denotes the vertex connectivity. In contrast, in a general graph the size of the mincut can be equal to kappa(G). This result is tight.

Development of pseudo-two-dimensional turbulent wakes

Pseudotwo-dimensional wakes are generated by introducing spanwise cellular structures into an otherwise plane turbulent wake by means of the castellated blunt trailing edges of different configurations. The transverse growths of these coflowing cellular wakes are found to be independent of each other without any noticeable spanwise interaction. This wake growth is examined in the light of the plane equilibrium wake analysis. Though these wakes are not found to be exactly self-similar, their growth shows a nonmonotonous approach toward the asymptotic state appropriate to that of a plane wake. The dye emission in the wakes illustrated a coherent vortical structure in the transverse plane, similar to that of the usual two-dimensional wake, in spite of the initial spanwise irregularities.

Application of the method of initial functions for the analysis of composite laminated plates

The method of initial functions has been applied for deriving higher order theories for cross-ply laminated composite thick rectangular plates. The equations of three-dimensional elasticity have been used. No a priori assumptions regarding the distribution of stresses or displacements are needed. Numerical solutions of the governing equations have been presented for simply supported edges and the results are compared with available ones.

Recognition And Top-Down Generation Of Beta-Acyclic Database Schemes

Database schemes can be viewed as hypergraphs with individual relation schemes corresponding to the edges of a hypergraph. Under this setting, a new class of "acyclic" database schemes was recently introduced and was shown to have a claim to a number of desirable properties. However, unlike the case of ordinary undirected graphs, there are several unequivalent notions of acyclicity of hypergraphs. Of special interest among these are agr-, beta-, and gamma-, degrees of acyclicity, each characterizing an equivalence class of desirable properties for database schemes, represented as hypergraphs. In this paper, two complementary approaches to designing beta-acyclic database schemes have been presented. For the first part, a new notion called "independent cycle" is introduced. Based on this, a criterion for beta-acyclicity is developed and is shown equivalent to the existing definitions of beta-acyclicity. From this and the concept of the dual of a hypergraph, an efficient algorithm for testing beta-acyclicity is developed. As for the second part, a procedure is evolved for top-down generation of beta-acyclic schemes and its correctness is established. Finally, extensions and applications of ideas are described.

Valence fluctuation in some Yb intermetallics by X-ray photoemission and X-ray absorption

The valence state of Yb in some of its intermetallics, YbNi2Ge2, YbCu2Si2 and YbPd2Si2 has been investigated by LIII(Yb) absorption edges and X-ray pnotoelectron spectra in the 4f and 4d regions. These studies establish the presence of mixed valence in all three systems and illustrate the utility of 4f and 4d spectra in the study of mixed valence in Yb compounds.

Transverse vibrations of hybrid laminated plates

In this paper, an attempt is made to obtain the free vibration response of hybrid, laminated rectangular and skew plates. The Galerkin technique is employed to obtain an approximate solution of the governing differential equations. It is found that this technique is well suited for the study of such problems. Results are presented in a graphical form for plates with one pair of opposite edges simply supported and the other two edges clamped. The method is quite general and can be applied to any other boundary conditions.

Finite element analysis of moving contact in mechanically fastened joints

The Finite Element Method (FEM) has made a number of otherwise intractable problems solvable. An important aspect for achieving an economical and accurate solution through FEM is matching the formulation and the computational organisation to the problem. This was realised forcefully in the present case of the solution of a class of moving contact boundary value problems of fastener joints. This paper deals with the problem of changing contact at the pin-hole interface of a fastener joint. Due to moving contact, the stresses and displacements are nonlinear with load. This would, in general, need an interactive-incremental approach for solution. However, by posing the problem in an inverse way, a solution is sought for obtaining loads to suit given contact configuration. Numerical results are given for typical isotropic and composite plates with rigid pins. Two cases of loading are considered: (i) load applied only at the edges of the plate and (ii) load applied at the pin and reacted at a part of the edge of the plate. Load-contact relationships, compliance and stress-patterns are investigated. This paper clearly demonstrates the simplification achieved by a suitable formulation of the problem. The results are of significance to the design and analysis of fastener joints.

Finite element analysis of moving contact in mechanically fastened joints

The Finite Element Method (FEM) has made a number of otherwise intractable problems solvable. An important aspect for achieving an economical and accurate solution through FEM is matching the formulation and the computational organisation to the problem. This was realised forcefully in the present case of the solution of a class of moving contact boundary value problems of fastener joints. This paper deals with the problem of changing contact at the pin-hole interface of a fastener joint. Due to moving contact, the stresses and displacements are nonlinear with load. This would, in general, need an interactive-incremental approach for solution. However, by posing the problem in an inverse way, a solution is sought for obtaining loads to suit given contact configuration. Numerical results are given for typical isotropic and composite plates with rigid pins. Two cases of loading are considered: (i) load applied only at the edges of the plate and (ii) load applied at the pin and reacted at a part of the edge of the plate. Load-contact relationships, compliance and stress-patterns are investigated. This paper clearly demonstrates the simplification achieved by a suitable formulation of the problem. The results are of significance to the design and analysis of fastener joints.

AC conductivity of a quantum Hall line junction

We present a microscopic model for calculating the AC conductivity of a finite length line junction made up of two counter-or co-propagating single mode quantum Hall edges with possibly different filling fractions. The effect of density-density interactions and a local tunneling conductance (sigma) between the two edges is considered. Assuming that sigma is independent of the frequency omega, we derive expressions for the AC conductivity as a function of omega, the length of the line junction and other parameters of the system. We reproduce the results of Sen and Agarwal (2008 Phys. Rev. B 78 085430) in the DC limit (omega -> 0), and generalize those results for an interacting system. As a function of omega, the AC conductivity shows significant oscillations if sigma is small; the oscillations become less prominent as sigma increases. A renormalization group analysis shows that the system may be in a metallic or an insulating phase depending on the strength of the interactions. We discuss the experimental implications of this for the behavior of the AC conductivity at low temperatures.

Optimal popular matchings

In this paper we consider the problem of computing an “optimal” popular matching. We assume that our input instance View the MathML source admits a popular matching and here we are asked to return not any popular matching but an optimal popular matching, where the definition of optimality is given as a part of the problem statement; for instance, optimality could be fairness in which case we are required to return a fair popular matching. We show an O(n2+m) algorithm for this problem, assuming that the preference lists are strict, where m is the number of edges in G and n is the number of applicants.

Application of molecular orbital theory to the interpretation of x-ray absorption spectra of platinum complexes

X-ray LIII-absorption edges of platinum in nine octahedral complexes have been recorded using a bent crystal spectrograph. The edge features of the discontinuities have been interpreted with the help of qualitative molecular orbital diagrams. A correlation between the energy separation of the first two absorption maxima and the spectrochemical series of the ligands has been arrived at.

Load-Deflection Behavior of Restrained R/C Skew Slabs

A method is presented for determining the complete load-deflection behavior of reinforced concrete skew slabs restrained at the edges and subjected to uniformly-distributed loading. The analysis is considered in three stages. In the first stage the load-deflection behavior up to the cracking load is considered. The behavior between the cracking load and the yield line load is considered in the second stage. The load-deflection behavior beyond the yield line load, taking into account the effect of the membrane action, is considered in the third stage. Details of an experimental program of casting and testing 12 reinforced concrete skew slabs restrained at the edges are presented to verify the results of the analysis.

Power dissipation for systems with junctions of multiple quantum wires

We study power dissipation for systems of multiple quantum wires meeting at a junction, in terms of a current splitting matrix (M) describing the junction. We present a unified framework for studying dissipation for wires with either interacting electrons (i.e., Tomonaga-Luttinger liquid wires with Fermi-liquid leads) or noninteracting electrons. We show that for a given matrix M, the eigenvalues of (MM)-M-T characterize the dissipation, and the eigenvectors identify the combinations of bias voltages which need to be applied to the different wires in order to maximize the dissipation associated with the junction. We use our analysis to propose and study some microscopic models of a dissipative junction which employ the edge states of a quantum Hall liquid. These models realize some specific forms of the M matrix whose entries depends on the tunneling amplitudes between the different edges.

Efficient computation of volume fractions for multi-material cell complexes in a grid by slicing

The paper presents a novel slicing based method for computation of volume fractions in multi-material solids given as a B-rep whose faces are triangulated and shared by either one or two materials. Such objects occur naturally in geoscience applications and the said computation is necessary for property estimation problems and iterative forward modeling. Each facet in the model is cut by the planes delineating the given grid structure or grid cells. The method, instead of classifying the points or cells with respect to the solid, exploits the convexity of triangles and the simple axis-oriented disposition of the cutting surfaces to construct a novel intermediate space enumeration representation called slice-representation, from which both the cell containment test and the volume-fraction computation are done easily. Cartesian and cylindrical grids with uniform and non-uniform spacings have been dealt with in this paper. After slicing, each triangle contributes polygonal facets, with potential elliptical edges, to the grid cells through which it passes. The volume fractions of different materials in a grid cell that is in interaction with the material interfaces are obtained by accumulating the volume contributions computed from each facet in the grid cell. The method is fast, accurate, robust and memory efficient. Examples illustrating the method and performance are included in the paper.