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.

Convenient construction of tetrahedral finite elements for the quasi-harmonic equation

It is shown that in the finite-element formulation of the general quasi-harmonic equation using tetrahedral elements, for every member of the element family there exists just one numerical universal matrix indpendent of the size, shape and material properties of the element. Thus the element matrix is conveniently constructed by manipulating this single matrix along with a set of reverse sequence codes at the same time accounting for the size, shape and material properties in a simple manner.

Construction of inverses with prescribed zero minors and applications to decentralized stabilization

We examine the following question: Suppose R is a principal ideal domain, and that F is an n × m matrix with elements in R, with n>m. When does there exist an m × n matrix G such that GF = Im, and such that certain prescribed minors of G equal zero? We show that there is a simple necessary condition for the existence of such a G, but that this condition is not sufficient in general. However, if the set of minors of G that are required to be zero has a certain pattern, then the condition is necessary as well as sufficient. We then show that the pattern mentioned above arises naturally in connection with the question of the existence of decentralized stabilizing controllers for a given plant. Hence our result allows us to derive an extremely simple proof of the fact that a necessary and sufficient condition for the existence of decentralized stabilizing controllers is the absence of unstable decentralized fixed modes, as well as to derive a very clean expression for these fixed modes. In addition to the application to decentralized stabilization, we believe that the result is of independent interest.

Signal set design for full-diversity low-decoding-complexity differential scaled-unitary STBCs

The problem of designing high rate, full diversity noncoherent space-time block codes (STBCs) with low encoding and decoding complexity is addressed. First, the notion of g-group encodable and g-group decodable linear STBCs is introduced. Then for a known class of rate-1 linear designs, an explicit construction of fully-diverse signal sets that lead to four-group encodable and four-group decodable differential scaled unitary STBCs for any power of two number of antennas is provided. Previous works on differential STBCs either sacrifice decoding complexity for higher rate or sacrifice rate for lower decoding complexity.

Signal set design for full-diversity low-decoding-complexity differential scaled-unitary STBCs

The problem of designing high rate, full diversity noncoherent space-time block codes (STBCs) with low encoding and decoding complexity is addressed. First, the notion of g-group encodable and g-group decodable linear STBCs is introduced. Then for a known class of rate-1 linear designs, an explicit construction of fully-diverse signal sets that lead to four-group encodable and four-group decodable differential scaled unitary STBCs for any power of two number of antennas is provided. Previous works on differential STBCs either sacrifice decoding complexity for higher rate or sacrifice rate for lower decoding complexity.

Construction and use of linear regression models for processor performance analysis

Processor architects have a challenging task of evaluating a large design space consisting of several interacting parameters and optimizations. In order to assist architects in making crucial design decisions, we build linear regression models that relate Processor performance to micro-architecture parameters, using simulation based experiments. We obtain good approximate models using an iterative process in which Akaike's information criteria is used to extract a good linear model from a small set of simulations, and limited further simulation is guided by the model using D-optimal experimental designs. The iterative process is repeated until desired error bounds are achieved. We used this procedure to establish the relationship of the CPI performance response to 26 key micro-architectural parameters using a detailed cycle-by-cycle superscalar processor simulator The resulting models provide a significance ordering on all micro-architectural parameters and their interactions, and explain the performance variations of micro-architectural techniques.

A facile regioselective construction of spiro epoxy-bridged tetrahydropyranone frameworks

Investigations on the reactivity profile of the transient five-membered-ring cyclic carbonyl ylides, generated from alpha-diazo ketones, in the presence of the C=O group of various simple ketones and symrnetrical/unsymmetrical 1,2-diones were carried out. The reaction of alpha-diazo ketones with 1,2-naphthoquinone furnished interesting diastereomeric cycloadducts in which both the C=O groups acted as dipolarophilic sites. The similar reaction in the presence of several isatin derivatives afforded novel spiro dioxa-bridged indole derivatives as a mixture of diastereomers. The single crystal X-ray structure analysis manifestly revealed the mode of cycloaddition and the stereochemistry of two of the diastereomers. A diverse set of novel spiro epoxy-bridged tetrahydropyranone frameworks have been constructed in good yield via the tandem cyclization-cycloaddition of alpha-diazo ketones with the C=O group as heterodipolarophile in a regioselective manner. (C) 2003 Elsevier Ltd. All rights reserved.

An O(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 Õ(mc) where |E| = m and c is the maximum u-vedge connectivity, where u,v ∈ 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 running time of our algorithm for simple unweighted graphs is Õ(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 Õ(n20/9) max flow algorithm due to Karger and Levine [11] yields the current best running time of Õ(n20/9n) for Gomory-Hu tree construction on simpleunweighted graphs with m edges and n vertices. Thus we present the first Õ(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 ⊆ V can be reused for computing a minimum Steiner cut for certain Steiner sets S' ⊆ S.

A general construction of space-time trellis codes for PSK signal sets

The diversity order and coding gain are crucial for the performance of a multiple antenna communication system. It is known that space-time trellis codes (STTC) can be used to achieve these objectives. In particular, we can use STTCs to obtain large coding gains. Many attempts have been made to construct STTCs which achieve full-diversity and good coding gains, though a general method of construction does not exist. Delay diversity code (rate-1) is known to achieve full-diversity, for any number of transmit antennas and any signal set, but does not give a good coding gain. A product distance code based delay diversity scheme (Tarokh, V. et al., IEEE Trans. Inform. Theory, vol.44, p.744-65, 1998) enables one to improve the coding gain and construct STTCs for any given number of states using coding in conjunction with delay diversity; it was stated as an open problem. We achieve such a construction. We assume a shift register based model to construct an STTC for any state complexity. We derive a sufficient condition for this STTC to achieve full-diversity, based on the delay diversity scheme. This condition provides a framework to do coding in conjunction with delay diversity for any signal constellation. Using this condition, we provide a formal rate-1 STTC construction scheme for PSK signal sets, for any number of transmit antennas and any given number of states, which achieves full-diversity and gives a good coding gain.

Construction of equivalent circuit of a transformer winding from driving-point impedance function - analytical approach

Analytical solution is presented to convert a given driving-point impedance function (in s-domain) into a physically realisable ladder network with inductive coupling between any two sections and losses considered. The number of sections in the ladder network can vary, but its topology is assumed fixed. A study of the coefficients of the numerator and denominator polynomials of the driving-point impedance function of the ladder network, for increasing number of sections, led to the identification of certain coefficients, which exhibit very special properties. Generalised expressions for these specific coefficients have also been derived. Exploiting their properties, it is demonstrated that the synthesis method essentially turns out to be an exercise of solving a set of linear, simultaneous, algebraic equations, whose solution directly yields the ladder network elements. The proposed solution is novel, simple and guarantees a unique network. Presently, the formulation can synthesise a unique ladder network up to six sections.

Construction of a Plasmodium falciparum Rab-interactome identifies CK1 and PKA as Rab-effector kinases in malaria parasites

Background information. The pathology causing stages of the human malaria parasite Plasmodium falciparum reside within red blood cells that are devoid of any regulated transport system. The parasite, therefore, is entirely responsible for mediating vesicular transport within itself and in the infected erythrocyte cytoplasm, and it does so in part via its family of 11 Rab GTPases. Putative functions have been ascribed to Plasmodium Rabs due to their homology with Rabs of yeast, particularly with Saccharomyces that has an equivalent number of rab/ypt genes and where analyses of Ypt function is well characterized. Results. Rabs are important regulators of vesicular traffic due to their capacity to recruit specific effectors. In order to identify P. falciparum Rab (PfRab) effectors, we first built a Ypt-interactome by exploiting genetic and physical binding data available at the Saccharomyces genome database (SGD). We then constructed a PfRab-interactome using putative parasite Rab-effectors identified by homology to Ypt-effectors. We demonstrate its potential by wet-bench testing three predictions; that casein kinase-1 (PfCK1) is a specific Rab5B interacting protein and that the catalytic subunit of cAMP-dependent protein kinase A (PfPKA-C) is a PfRab5A and PfRab7 effector. Conclusions. The establishment of a shared set of physical Ypt/PfRab-effector proteins sheds light on a core set Plasmodium Rab-interactants shared with yeast. The PfRab-interactome should benefit vesicular trafficking studies in malaria parasites. The recruitment of PfCK1 to PfRab5B+ and PfPKA-C to PfRab5A+ and PfRab7+ vesicles, respectively, suggests that PfRab-recruited kinases potentially play a role in early and late endosome function in malaria parasites.

OPTIMALITY OF THE PRODUCT-MATRIX CONSTRUCTION FOR SECURE MSR REGENERATING CODES

In this paper, we consider the security of exact-repair regenerating codes operating at the minimum-storage-regenerating (MSR) point. The security requirement (introduced in Shah et. al.) is that no information about the stored data file must be leaked in the presence of an eavesdropper who has access to the contents of l(1) nodes as well as all the repair traffic entering a second disjoint set of l(2) nodes. We derive an upper bound on the size of a data file that can be securely stored that holds whenever l(2) <= d - k +1. This upper bound proves the optimality of the product-matrix-based construction of secure MSR regenerating codes by Shah et. al.

Explicit and Unique Construction of Tetrablock Unitary Dilation in a Certain Case

Consider the domain E in defined by This is called the tetrablock. This paper constructs explicit boundary normal dilation for a triple (A, B, P) of commuting bounded operators which has as a spectral set. We show that the dilation is minimal and unique under a certain natural condition. As is well-known, uniqueness of minimal dilation usually does not hold good in several variables, e.g., Ando's dilation is known to be not unique, see Li and Timotin (J Funct Anal 154:1-16, 1998). However, in the case of the tetrablock, the third component of the dilation can be chosen in such a way as to ensure uniqueness.

Steam-cured stabilised soil blocks for masonry construction

Energy-efficient, economical and durable building materials are essential for sustainable construction practices. The paper deals with production and properties of energy-efficient steam-cured stabilised soil blocks used fbr masonry construction. Problems of mixing expansive soil and lime, and production of blocks using soil-lime mixtures have been discussed briefly. Details of steam curing of stabilised soil blocks and properties of such blocks are given. A comparison of energy content of steam-cured soil blocks and burnt bricks is presented. It has been shown that energy-efficient steam cured soil blocks (consuming 35% less thermal energy compared to burnt clay bricks) having high compressive strength can be easily produced in a decentralised manner.

Efficient Output-Sensitive Construction of Reeb Graphs

The Reeb graph tracks topology changes in level sets of a scalar function and finds applications in scientific visualization and geometric modeling. This paper describes a near-optimal two-step algorithm that constructs the Reeb graph of a Morse function defined over manifolds in any dimension. The algorithm first identifies the critical points of the input manifold, and then connects these critical points in the second step to obtain the Reeb graph. A simplification mechanism based on topological persistence aids in the removal of noise and unimportant features. A radial layout scheme results in a feature-directed drawing of the Reeb graph. Experimental results demonstrate the efficiency of the Reeb graph construction in practice and its applications.