Finding a Box Representation for a Graph in $O(n^2\Delta^2\ln n)$ time

An axis-parallel box in $b$-dimensional space is a Cartesian product $R_1 \times R_2 \times \cdots \times R_b$ where $R_i$ (for $1 \leq i \leq b$) is a closed interval of the form $[a_i, b_i]$ on the real line. For a graph $G$, its boxicity is the minimum dimension $b$, such that $G$ is representable as the intersection graph of (axis-parallel) boxes in $b$-dimensional space. The concept of boxicity finds application in various areas of research like ecology, operation research etc. Chandran, Francis and Sivadasan gave an $O(\Delta n^2 \ln^2 n)$ randomized algorithm to construct a box representation for any graph $G$ on $n$ vertices in $\lceil (\Delta + 2)\ln n \rceil$ dimensions, where $\Delta$ is the maximum degree of the graph. They also came up with a deterministic algorithm that runs in $O(n^4 \Delta )$ time. Here, we present an $O(n^2 \Delta^2 \ln n)$ deterministic algorithm that constructs the box representation for any graph in $\lceil (\Delta + 2)\ln n \rceil$ dimensions.

Scan cell reordering to minimize peak power during test cycle: A graph theoretic approach

Scan circuit is widely practiced DFT technology. The scan testing procedure consist of state initialization, test application, response capture and observation process. During the state initialization process the scan vectors are shifted into the scan cells and simultaneously the responses captured in last cycle are shifted out. During this shift operation the transitions that arise in the scan cells are propagated to the combinational circuit, which inturn create many more toggling activities in the combinational block and hence increases the dynamic power consumption. The dynamic power consumed during scan shift operation is much more higher than that of normal mode operation.

Evolving Random Geometric Graph Models for Mobile Wireless Networks

We consider evolving exponential RGGs in one dimension and characterize the time dependent behavior of some of their topological properties. We consider two evolution models and study one of them detail while providing a summary of the results for the other. In the first model, the inter-nodal gaps evolve according to an exponential AR(1) process that makes the stationary distribution of the node locations exponential. For this model we obtain the one-step conditional connectivity probabilities and extend it to the k-step case. Finite and asymptotic analysis are given. We then obtain the k-step connectivity probability conditioned on the network being disconnected. We also derive the pmf of the first passage time for a connected network to become disconnected. We then describe a random birth-death model where at each instant, the node locations evolve according to an AR(1) process. In addition, a random node is allowed to die while giving birth to a node at another location. We derive properties similar to those above.

Evidence of residual entropy in the cubic spinel Zn2TiO4

The standard free energies of formation of Zn2Ti04 and ZnTi03 have been determined in the temperature range 930° to i ioo'x from electromotive force measurements on reversible solid oxide galvanic cells;Ag-5at%znll I Pt, + CaO-Zr02 ZnO I II Ag-5at%Zn Y20r Th02 CaO-Zr02 + ,Pt Zn2Ti04+ ZnTi03 and II Ag-5at%Zn CaO-Zr02 + ,Pt ZnTi03+ Ti02 The values may be expressed by the equations,2ZnO (wurtz) + Ti02(rut) -> Zn2Ti04(sp), f:!:.Go = -750-2-46T (±75)cal;ZnO(wurtz) +Ti02(rut) -> ZnTi03(ilmen) ,f:!:.Co = -]600-0·]99T(±50)cal.Combination of the free energy values with the calorimetric heat of formation, and low-temperature and high-temperature heat capacity of Zn2Ti04 reported in literature, suggests a residual entropy of ],9 (±0·6) cal K-1 mol ? for the cubic spinel. Ideal mixing of Zn2+ and Ti4+ ions on the octahedral sites would result in a configurational contribution to the entropy of 2· 75 cal K-1 rnol ".The difference is indicative of short-range ordering of cations on octahedral sites.

An entropy meter based on the thermoelectric potential of a nonisothermal solid electrolyte cell

The theory, design, and performance of a solid electrolyte twin thermocell for the direct determination of the partial molar entropy of oxygen in a single-phase or multiphase mixture are described. The difference between the Seebeck coefficients of the concentric thermocells is directly related to the difference in the partial molar entropy of oxygen in the electrodes of each thermocell. The measured potentials are sensitive to small deviations from equilibrium at the electrodes. Small electric disturbances caused by simultaneous potential measurements or oxygen fluxes caused by large oxygen potential gradients between the electrodes also disturb the thermoelectric potential. An accuracy of ±0.5 calth K−1 mol−1 has been obtained by this method for the entropies of formation of NiO and NiAl2O4. This “entropy meter” may be used for the measurement of the entropies of formation of simple or complex oxides with significant residual contributions which cannot be detected by heat-capacity measurements.

The standard enthalpy and entropy of formation of Rh2O3 - A third-law optimization

The standard Gibbs energy of formation of Rh203 at high temperature has been determined recently with high precision. The new data are significantly different from those given in thermodynamic compilations.Accurate values for enthalpy and entropy of formation at 298.15 K could not be evaluated from the new data,because reliable values for heat capacity of Rh2O3 were not available. In this article, a new measurement of the high temperature heat capacity of Rh2O3 using differential scanning calorimetry (DSC) is presented.The new values for heat capacity also differ significantly from those given in compilations. The information on heat capacity is coupled with standard Gibbs energy of formation to evaluate values for standard enthalpy and entropy of formation at 289.15 K using a multivariate analysis. The results suggest a major revision in thermodynamic data for Rh2O3. For example, it is recommended that the standard entropy of Rh203 at 298.15 K be changed from 106.27 J mol-' K-'given in the compilations of Barin and Knacke et al. to 75.69 J mol-' K". The recommended revision in the standard enthalpy of formation is from -355.64 kJ mol-'to -405.53 kJ mol".

Magnetic Field Dependence of Entropy And Specific Heat of YBa2Cu3O7-delta Superconductors

The change in thermodynamic quantities (e. g., entropy, specific heat etc.) by the application of magnetic field in the case of the high-T-c superconductor YBCO system is examined phenomenological by the Ginzburg-Landau theory of anisotropic type-II superconductors. An expression for the change in the entropy (Delta S) and change in specific heat (Delta C) in a magnetic field for any general orientation of an applied magnetic field B-a with respect to the crystallographic c-axis is obtained. The observed large reduction of specific heat anomaly just below the superconducting transition and the observed variation of entropy with magnetic field are explained quantitatively.

An (O)over-bar(m(2)n) randomized algorithm to compute a minimum cycle basis of a directed graph

We consider the problem of computing a minimum cycle basis in a directed graph G. The input to this problem is a directed graph whose arcs have positive weights. In this problem a {- 1, 0, 1} incidence vector is associated with each cycle and the vector space over Q generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of weights of the cycles is minimum is called a minimum cycle basis of G. The current fastest algorithm for computing a minimum cycle basis in a directed graph with m arcs and n vertices runs in O(m(w+1)n) time (where w < 2.376 is the exponent of matrix multiplication). If one allows randomization, then an (O) over tilde (m(3)n) algorithm is known for this problem. In this paper we present a simple (O) over tilde (m(2)n) randomized algorithm for this problem. The problem of computing a minimum cycle basis in an undirected graph has been well-studied. In this problem a {0, 1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of the graph. The fastest known algorithm for computing a minimum cycle basis in an undirected graph runs in O(m(2)n + mn(2) logn) time and our randomized algorithm for directed graphs almost matches this running time.

Statistical properties of entropy-consuming fluctuations in jammed states of laponite suspensions: Fluctuation relations and generalized Gumbel distribution

We report a universal large deviation behavior of spatially averaged global injected power just before the rejuvenation of the jammed state formed by an aging suspension of laponite clay under an applied stress. The probability distribution function (PDF) of these entropy consuming strongly non-Gaussian fluctuations follow an universal large deviation functional form described by the generalized Gumbel (GG) distribution like many other equilibrium and nonequilibrium systems with high degree of correlations but do not obey the Gallavotti-Cohen steady-state fluctuation relation (SSFR). However, far from the unjamming transition (for smaller applied stresses) SSFR is satisfied for both Gaussian as well as non-Gaussian PDF. The observed slow variation of the mean shear rate with system size supports a recent theoretical prediction for observing GG distribution.

Transport in nanoporous zeolites: Relationships between sorbate size, entropy, and diffusivity

Molecular dynamics simulations have been performed on monatomic sorbates confined within zeolite NaY to obtain the dependence of entropy and self-diffusivity on the sorbate diameter. Previously, molecular dynamics simulations by Santikary and Yashonath J. Phys. Chem. 98, 6368 (1994)], theoretical analysis by Derouane J. Catal. 110, 58 (1988)] as well as experiments by Kemball Adv. Catal. 2, 233 (1950)] found that certain sorbates in certain adsorbents exhibit unusually high self-diffusivity. Experiments showed that the loss of entropy for certain sorbates in specific adsorbents was minimum. Kemball suggested that such sorbates will have high self-diffusivity in these adsorbents. Entropy of the adsorbed phase has been evaluated from the trajectory information by two alternative methods: two-phase and multiparticle expansion. The results show that anomalous maximum in entropy is also seen as a function of the sorbate diameter. Further, the experimental observation of Kemball that minimum loss of entropy is associated with maximum in self-diffusivity is found to be true for the system studied here. A suitably scaled dimensionless self-diffusivity shows an exponential dependence on the excess entropy of the adsorbed phase, analogous to excess entropy scaling rules seen in many bulk and confined fluids. The two trajectory-based estimators for the entropy show good semiquantitative agreement and provide some interesting microscopic insights into entropy changes associated with confinement.

On maximum entropy and minimum KL-divergence optimization by Grobner basis methods

In this paper we study constrained maximum entropy and minimum divergence optimization problems, in the cases where integer valued sufficient statistics exists, using tools from computational commutative algebra. We show that the estimation of parametric statistical models in this case can be transformed to solving a system of polynomial equations. We give an implicit description of maximum entropy models by embedding them in algebraic varieties for which we give a Grobner basis method to compute it. In the cases of minimum KL-divergence models we show that implicitization preserves specialization of prior distribution. This result leads us to a Grobner basis method to embed minimum KL-divergence models in algebraic varieties. (C) 2012 Elsevier Inc. All rights reserved.

Bond Graph Modeling for Energy-Harvesting Wireless Sensor Networks

Researchers can use bond graph modeling, a tool that takes into account the energy conservation principle, to accurately assess the dynamic behavior of wireless sensor networks on a continuous basis.