Geometric Representation of Graphs in Low Dimension Using Axis Parallel Boxes

An axis-parallel k-dimensional box is a Cartesian product R-1 x R-2 x...x R-k where R-i (for 1 <= i <= k) is a closed interval of the form [a(i), b(i)] on the real line. For a graph G, its boxicity box(G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem for boxicity d graphs, given a box representation, has a left perpendicular1 + 1/c log n right perpendicular(d-1) approximation ratio for any constant c >= 1 when d >= 2. In most cases, the first step usually is computing a low dimensional box representation of the given graph. Deciding whether the boxicity of a graph is at most 2 itself is NP-hard. We give an efficient randomized algorithm to construct a box representation of any graph G on n vertices in left perpendicular(Delta + 2) ln nright perpendicular dimensions, where Delta is the maximum degree of G. This algorithm implies that box(G) <= left perpendicular(Delta + 2) ln nright perpendicular for any graph G. Our bound is tight up to a factor of ln n. We also show that our randomized algorithm can be derandomized to get a polynomial time deterministic algorithm. Though our general upper bound is in terms of maximum degree Delta, we show that for almost all graphs on n vertices, their boxicity is O(d(av) ln n) where d(av) is the average degree.

Study Of The Hvdc-Torsional Interactions Through Digital Dynamic Simulation

This paper presents the detailed dynamic digital simulation for the study of phenomenon of torsional interaction between HVDC-Turbine generator shaft, dynamics using the novel converter model presented in [ 1 ] The system model includes detailed representation of the synchronous generator and the shaft dynamics, the ac and dc network transients. The results of a case study indicate the various factors that influence the torsional interaction.

Space and time efficiency of the forest-of-quadtrees representation

A forest of quadtrees is a refinement of a quadtree data structure that is used to represent planar regions. A forest of quadtrees provides space savings over regular quadtrees by concentrating vital information. The paper presents some of the properties of a forest of quadtrees and studies the storage requirements for the case in which a single 2m × 2m region is equally likely to occur in any position within a 2n × 2n image. Space and time efficiency are investigated for the forest-of-quadtrees representation as compared with the quadtree representation for various cases.

Software simulation of the EEG

The literature contains many examples of digital procedures for the analytical treatment of electroencephalograms, but there is as yet no standard by which those techniques may be judged or compared. This paper proposes one method of generating an EEG, based on a computer program for Zetterberg's simulation. It is assumed that the statistical properties of an EEG may be represented by stationary processes having rational transfer functions and achieved by a system of software fillers and random number generators.The model represents neither the neurological mechanism response for generating the EEG, nor any particular type of EEG record; transient phenomena such as spikes, sharp waves and alpha bursts also are excluded. The basis of the program is a valid ‘partial’ statistical description of the EEG; that description is then used to produce a digital representation of a signal which if plotted sequentially, might or might not by chance resemble an EEG, that is unimportant. What is important is that the statistical properties of the series remain those of a real EEG; it is in this sense that the output is a simulation of the EEG. There is considerable flexibility in the form of the output, i.e. its alpha, beta and delta content, which may be selected by the user, the same selected parameters always producing the same statistical output. The filtered outputs from the random number sequences may be scaled to provide realistic power distributions in the accepted EEG frequency bands and then summed to create a digital output signal, the ‘stationary EEG’. It is suggested that the simulator might act as a test input to digital analytical techniques for the EEG, a simulator which would enable at least a substantial part of those techniques to be compared and assessed in an objective manner. The equations necessary to implement the model are given. The program has been run on a DEC1090 computer but is suitable for any microcomputer having more than 32 kBytes of memory; the execution time required to generate a 25 s simulated EEG is in the region of 15 s.

STBC's from representation of extended Clifford Algebras

A set of sufficient conditions to construct lambda-real symbol Maximum Likelihood (ML) decodable STBCs have recently been provided by Karmakar et al. STBCs satisfying these sufficient conditions were named as Clifford Unitary Weight (CUW) codes. In this paper, the maximal rate (as measured in complex symbols per channel use) of CUW codes for lambda = 2(a), a is an element of N is obtained using tools from representation theory. Two algebraic constructions of codes achieving this maximal rate are also provided. One of the constructions is obtained using linear representation of finite groups whereas the other construction is based on the concept of right module algebra over non-commutative rings. To the knowledge of the authors, this is the first paper in which matrices over non-commutative rings is used to construct STBCs. An algebraic explanation is provided for the 'ABBA' construction first proposed by Tirkkonen et al and the tensor product construction proposed by Karmakar et al. Furthermore, it is established that the 4 transmit antenna STBC originally proposed by Tirkkonen et al based on the ABBA construction is actually a single complex symbol ML decodable code if the design variables are permuted and signal sets of appropriate dimensions are chosen.

Holographic optical elements: State-of-the-art review: Part 2

This is the second part of a two part review on the state-of-the-art in holographic optical elements (HOEs). The aspects of fabrication, evaluation, and applications of HOEs, are discussed in this part. It details the direction of future efforts towards finding work-horse type recording media, developing new methods for the evaluation of HOE, and identifying the areas of application where HOEs are to be considered as indispensable components/tools. Finally a summary of all the suggestions for future work made in the two parts is displayed in Table 2 of this part of the review.

Structure and representation of correlation functions and the density matrix for a statistical wave field in optics

A systematic structure analysis of the correlation functions of statistical quantum optics is carried out. From a suitably defined auxiliary two‐point function we are able to identify the excited modes in the wave field. The relative simplicity of the higher order correlation functions emerge as a byproduct and the conditions under which these are made pure are derived. These results depend in a crucial manner on the notion of coherence indices and of unimodular coherence indices. A new class of approximate expressions for the density operator of a statistical wave field is worked out based on discrete characteristic sets. These are even more economical than the diagonal coherent state representations. An appreciation of the subtleties of quantum theory obtains. Certain implications for the physics of light beams are cited.

A field-consistent and variationally correct representation of transverse shear strains in the nine-noded plate element

We present a biquadratic Lagrangian plate bending element with consistent fields for the constrained transverse shear strain functions. A technique involving expansion of the strain interpolations in terms of Legendre polynomials is used to redistribute the kinematically derived shear strain fields so that the field-consistent forms (i.e. avoiding locking) are also variationally correct (i.e. do not violate the variational norms). Also, a rational method of isoparametric Jacobian transformation is incorporated so that the constrained covariant shear strain fields are always consistent in whatever general quadrilateral form the element may take. Finally the element is compared with another formulation which was recently published. The element is subjected to several robust bench mark tests and is found to pass all the tests efficiently.

Flat rotation curves: A result of the helical inverse cascade in turbulent media

We have modeled the rotation curves of 21 galaxies observed by Amram et al. (1992), by combining the effects of rigid rotation, gravity, and turbulence. The main motivation behind such modeling is to study the formation of coherent structures in turbulent media and explore its role in the large-scale structures of the universe. The values of the parameters such as mass, turbulent velocity, and angular velocity derived from the rotation curve fits are in good agreement with those derived from the prevalent models.

Integral treatment for the representation of thermodynamic properties in multicomponent systems using interaction parameters

The partial thermodynamic functions of the solvent component of a ternary system have been deduced in terms of the interaction parameters by integration of several series which emerge from the Maclaurin infinite series based on the integral property of the system and subjected to appropriate boundary conditions. The series integration shows that the resulting partial functions are suitable for interpreting the thermodynamic properties of the system and are independent of compositional paths. In the present analysis, the higher order terms of these series are found to make insignificant contributions.

C-13 MAS NMR spectra of cis,cis-mucononitrile in liquid-crystalline media and in the solid state. Orientation of the carbon chemical-shift tensors

The spinning sidebands observed in the C-13 MAS NMR spectra of cis,cis-mucononitrile oriented in liquid-crystalline media and of the neat sample in the solid state are studied. There are differences in the sideband intensity patterns in the two cases. These differences arise because the order parameters which characterize the orientation of the solute in the liquid-crystalline media differ for different axes. It is shown that, in general, the relative intensities of the sidebands contain information on the sign and magnitude of an effective chemical-shift parameter which is a function of the sum of the products of the principal components of the chemical-shift tensor and the corresponding order parameters with respect to the director. A method for obtaining the orientation of the carbon chemical-shift tensor is proposed. The carbon chemical-shift tensors obtained from gauge-including atomic orbital calculations are also presented for comparison. (C) 1996 Academic Press, Inc.

Representation of thermodynamic properties of ternary systems and its application to the system silver-gold-copper at 1350 K

The article presents a generalized analytical expression for description of the integral excess Gibbs free energy of mixing of a ternary system. Twelve constants of the equation are assessed by the least mean squares regressional analysis of the experimental integral excess data of the constituent binaries; three ternary parameters are evaluated by a regressional analysis based on the partial experimental data of a component of the ternary system. The assessed values of the ternary parameters describe the nature of the ternary interaction in the system. Activities and isoactivities of the components in the Ag-Au-Cu system at 1350 K are calculated and found to be in good agreement with the experimental data. This analytical treatment is particularly useful to ternary systems where the thermodynamic data are available from different sources.

Generalized eigenvalue decomposition of the field autocorrelation in correlation diffusion of photons in turbid media

We propose a novel numerical method based on a generalized eigenvalue decomposition for solving the diffusion equation governing the correlation diffusion of photons in turbid media. Medical imaging modalities such as diffuse correlation tomography and ultrasound-modulated optical tomography have the (elliptic) diffusion equation parameterized by a time variable as the forward model. Hitherto, for the computation of the correlation function, the diffusion equation is solved repeatedly over the time parameter. We show that the use of a certain time-independent generalized eigenfunction basis results in the decoupling of the spatial and time dependence of the correlation function, thus allowing greater computational efficiency in arriving at the forward solution. Besides presenting the mathematical analysis of the generalized eigenvalue problem on the basis of spectral theory, we put forth the numerical results that compare the proposed numerical method with the standard technique for solving the diffusion equation.

Role of the loop L-4,L-5 in allosteric regulation in mtHsp70s: in vivo significance of domain communication and its implications in protein translocation

Mitochondrial Hsp70 (mtHsp70) is essential for a vast repertoire of functions, including protein import, and requires effective interdomain communication for efficient partner-protein interactions. However, the in vivo functional significance of allosteric regulation in eukaryotes is poorly defined. Using integrated biochemical and yeast genetic approaches, we provide compelling evidence that a conserved substrate-binding domain (SBD) loop, L-4,L-5, plays a critical role in allosteric communication governing mtHsp70 chaperone functions across species. In yeast, a temperature-sensitive L-4,L-5 mutation (E467A) disrupts bidirectional domain communication, leading to compromised protein import and mitochondrial function. Loop L-4,L-5 functions synergistically with the linker in modulating the allosteric interface and conformational transitions between SBD and the nucleotide-binding domain (NBD), thus regulating interdomain communication. Second-site intragenic suppressors of E467A isolated within the SBD suppress domain communication defects by conformationally altering the allosteric interface, thereby restoring import and growth phenotypes. Strikingly, the suppressor mutations highlight that restoration of communication from NBD to SBD alone is the minimum essential requirement for effective in vivo function when primed at higher basal ATPase activity, mimicking the J-protein-bound state. Together these findings provide the first mechanistic insights into critical regions within the SBD of mtHsp70s regulating interdomain communication, thus highlighting its importance in protein translocation and mitochondrial biogenesis.