A constant factor approximation algorithm for boxicity of circular arc graphs

Boxicity of a graph G(V, E) is the minimum integer k such that G can be represented as the intersection graph of k-dimensional axis parallel boxes in Rk. Equivalently, it is the minimum number of interval graphs on the vertex set V such that the intersection of their edge sets is E. It is known that boxicity cannot be approximated even for graph classes like bipartite, co-bipartite and split graphs below O(n0.5-ε)-factor, for any ε > 0 in polynomial time unless NP = ZPP. Till date, there is no well known graph class of unbounded boxicity for which even an nε-factor approximation algorithm for computing boxicity is known, for any ε < 1. In this paper, we study the boxicity problem on Circular Arc graphs - intersection graphs of arcs of a circle. We give a (2+ 1/k)-factor polynomial time approximation algorithm for computing the boxicity of any circular arc graph along with a corresponding box representation, where k ≥ 1 is its boxicity. For Normal Circular Arc(NCA) graphs, with an NCA model given, this can be improved to an additive 2-factor approximation algorithm. The time complexity of the algorithms to approximately compute the boxicity is O(mn+n2) in both these cases and in O(mn+kn2) which is at most O(n3) time we also get their corresponding box representations, where n is the number of vertices of the graph and m is its number of edges. The additive 2-factor algorithm directly works for any Proper Circular Arc graph, since computing an NCA model for it can be done in polynomial time.

Cubicity, degeneracy, and crossing number

A $k$-box $B=(R_1,...,R_k)$, where each $R_i$ is a closed interval on the real line, is defined to be the Cartesian product $R_1\times R_2\times ...\times R_k$. If each $R_i$ is a unit length interval, we call $B$ a $k$-cube. Boxicity of a graph $G$, denoted as $\boxi(G)$, is the minimum integer $k$ such that $G$ is an intersection graph of $k$-boxes. Similarly, the cubicity of $G$, denoted as $\cubi(G)$, is the minimum integer $k$ such that $G$ is an intersection graph of $k$-cubes. It was shown in [L. Sunil Chandran, Mathew C. Francis, and Naveen Sivadasan: Representing graphs as the intersection of axis-parallel cubes. MCDES-2008, IISc Centenary Conference, available at CoRR, abs/cs/ 0607092, 2006.] that, for a graph $G$ with maximum degree $\Delta$, $\cubi(G)\leq \lceil 4(\Delta +1)\log n\rceil$. In this paper, we show that, for a $k$-degenerate graph $G$, $\cubi(G) \leq (k+2) \lceil 2e \log n \rceil$. Since $k$ is at most $\Delta$ and can be much lower, this clearly is a stronger result. This bound is tight. We also give an efficient deterministic algorithm that runs in $O(n^2k)$ time to output a $8k(\lceil 2.42 \log n\rceil + 1)$ dimensional cube representation for $G$. An important consequence of the above result is that if the crossing number of a graph $G$ is $t$, then $\boxi(G)$ is $O(t^{1/4}{\lceil\log t\rceil}^{3/4})$ . This bound is tight up to a factor of $O((\log t)^{1/4})$. We also show that, if $G$ has $n$ vertices, then $\cubi(G)$ is $O(\log n + t^{1/4}\log t)$. Using our bound for the cubicity of $k$-degenerate graphs we show that cubicity of almost all graphs in $\mathcal{G}(n,m)$ model is $O(d_{av}\log n)$, where $d_{av}$ denotes the average degree of the graph under consideration. model is O(davlogn).

Microstructure and tensile properties of consolidated magnesium chips

In this study tensile properties of consolidated magnesium chips obtained from solid state re-cycling (SSR) has been examined and correlated with the microstructure. Chips machined from as-cast billet of pure magnesium were consolidated through SSR technique, comprising of compaction at ambient conditions followed by hot extrusion at four different temperatures viz., 250, 300, 350 and 400 degrees C. The extruded rods were characterized for microstructure and their room temperature tensile properties. Both ultimate tensile strength and 0.2% proof stress of these consolidated materials are higher by 15-35% compared to reference material (as cast and extruded). Further these materials obey Hall-Petch relation with respect to strength dependence of grain size. Strain hardening behavior, measured in terms of hardening exponent, hardening capacity and hardening rate was found to be distinctly different in chip consolidated material compared to reference material. Strength asymmetry, measured as a ratio of compressive proof stress to tensile proof stress was higher in chip consolidated material. (C) 2012 Elsevier B.V. All rights reserved.

System Gd-Rh-O: Thermodynamics and phase relations

Thermodynamic properties of GdRhO3 are investigated in the temperature range from 900 to 1300 K by employing a solid-state electrochemical cell, incorporating calcia-stabilized zirconia as the electrolyte. The standard Gibbs free energy of formation of GdRhO3 from component binary oxide Gd2O3 with C-rare earth structure and Rh2O3 with orthorhombic structure can be expressed as; Delta G(f(ox))(o)(+/- 60)/J mol(-1) = -56603 + 3.78(T/K) Based on the thermodynamic information on GdRhO3 from experiment and auxiliary data for binary oxides from the literature and estimated properties of Gd-Rh alloys, phase relations are computed for the system Gd-Rh-O at 1273 K. Gibbs free energies for intermetallic phases in the binary Gd-Rh are evaluated using calorimetric data available in the literature for two compositions and Miedema's model, consistent with the binary phase diagram. Isothermal section of the ternary phase diagram, oxygen potential-composition diagram and a 3-D chemical potential diagram for the system Gd-Rh-O at 1273 K are developed. Phase relations in the ternary Gd-Rh-O are also computed as a function of temperature at constant oxygen partial pressures. The ternary oxide, GdRhO3 decomposes to Gd2O3 with B-rare earth structure, metallic Rh and O-2 at 1759(+/- 2) K in pure O-2 and 1649(+/- 2) K in air at a total pressure P-0 -0.1 MPa. (c) 2012 Elsevier B.V. All rights reserved.

Rice LHS1/OsMADS1 Controls Floret Meristem Specification by Coordinated Regulation of Transcription Factors and Hormone Signaling Pathways

SEPALLATA (SEP) MADS box transcription factors mediate floral development in association with other regulators. Mutants in five rice (Oryza sativa) SEP genes suggest both redundant and unique functions in panicle branching and floret development. LEAFY HULL STERILE1/OsMADS1, from a grass-specific subgroup of LOFSEP genes, is required for specifying a single floret on the spikelet meristem and for floret organ development, but its downstream mechanisms are unknown. Here, key pathways and directly modulated targets of OsMADS1 were deduced from expression analysis after its knockdown and induction in developing florets and by studying its chromatin occupancy at downstream genes. The negative regulation of OsMADS34, another LOFSEP gene, and activation of OsMADS55, a SHORT VEGETATIVE PHASE-like floret meristem identity gene, show its role in facilitating the spikelet-to-floret meristem transition. Direct regulation of other transcription factor genes like OsHB4 (a class III homeodomain Leu zipper member), OsBLH1 (a BEL1-like homeodomain member), OsKANADI2, OsKANADI4, and OsETTIN2 show its role in meristem maintenance, determinacy, and lateral organ development. We found that the OsMADS1 targets OsETTIN1 and OsETTIN2 redundantly ensure carpel differentiation. The multiple effects of OsMADS1 in promoting auxin transport, signaling, and auxin-dependent expression and its direct repression of three cytokinin A-type response regulators show its role in balancing meristem growth, lateral organ differentiation, and determinacy. Overall, we show that OsMADS1 integrates transcriptional and signaling pathways to promote rice floret specification and development.

Representing a cubic graph as the intersection graph of axis-parallel boxes in three dimensions

We show that every graph of maximum degree 3 can be represented as the intersection graph of axis parallel boxes in three dimensions, that is, every vertex can be mapped to an axis parallel box such that two boxes intersect if and only if their corresponding vertices are adjacent. In fact, we construct a representation in which any two intersecting boxes just touch at their boundaries. Further, this construction can be realized in linear time.

Modeling the dynamic response of wrap-faced reinforced soil retaining walls

This paper describes the development of a numerical model for simulating the shaking table tests on wrap-faced reinforced soil retaining walls. Some of the physical model tests carried out on reinforced soil retaining walls subjected to dynamic excitation through uniaxial shaking tests are briefly discussed. Models of retaining walls are constructed in a perspex box with geotextile reinforcement using the wraparound technique with dry sand backfill and instrumented with displacement sensors, accelerometers, and soil pressure sensors. Results showed that the displacements decrease with the increase in number of reinforcement layers, whereas acceleration amplifications were not affected significantly. Numerical modeling of these shaking table tests is carried out using the Fast Lagrangian Analysis of Continua program. The numerical model is validated by comparing the results with experiments on physical models. Responses of wrap-faced walls with varying numbers of reinforcement layers are compared. Sensitivity analysis performed on the numerical models showed that the friction and dilation angle of backfill material and stiffness properties of the geotextile-soil interface are the most affecting parameters for the model response.

Guided Ultrasonic Wave Propagation through Inaccessible Damage in a Folded Plate using Sensor-Actuator Network

Rapid diagnostics and virtual imaging of damages in complex structures like folded plate can help reduce the inspection time for guided wave based NDE and integrated SHM. Folded plate or box structure is one of the major structural components for increasing the structural strength. Damage in the folded plate, mostly in the form of surface breaking cracks in the inaccessible zone is a usual problem in aerospace structures. One side of the folded plate is attached (either riveted or bonded) to adjacent structure which is not accessible for immediate inspection. The sensor-actuator network in the form of a circular array is placed on the accessible side of the folded plate. In the present work, a circular array is employed for scanning the entire folded plate type structure for damage diagnosis and wave field visualization of entire structural panel. The method employs guided wave with relatively low frequency bandwidth of 100-300 kHz. Change in the response signal with respect to a baseline signal is used to construct a quantitative relationship with damage size parameters. Detecting damage in the folded plate by using this technique has significant potential for off-line and on-line SHM technologies. By employing this technique, surface breaking cracks on inaccessible face of the folded plate are detected without disassembly of structure in a realistic environment.

Subttractors

We consider extremal limits of the recently constructed ``subtracted geometry''. We show that extremality makes the horizon attractive against scalar perturbations, but radial evolution of such perturbations changes the asymptotics: from a conical-box to flat Minkowski. Thus these are black holes that retain their near-horizon geometry under perturbations that drastically change their asymptotics. We also show that this extremal subtracted solution (''subttractor'') can arise as a boundary of the basin of attraction for flat space attractors. We demonstrate this by using a fairly minimal action (that has connections with STU model) where the equations of motion are integrable and we are able to find analytic solutions that capture the flow from the horizon to the asymptotic region. The subttractor is a boundary between two qualitatively different flows. We expect that these results have generalizations for other theories with charged dilatonic black holes.

Vorticity moments in four numerical simulations of the 3D Navier-Stokes equations

The issue of intermittency in numerical solutions of the 3D Navier-Stokes equations on a periodic box 0, L](3) is addressed through four sets of numerical simulations that calculate a new set of variables defined by D-m(t) = (pi(-1)(0) Omega(m))(alpha m) for 1 <= m <= infinity where alpha(m) = 2m/(4m - 3) and Omega(m)(t)](2m) = L-3 integral(v) vertical bar omega vertical bar(2m) dV with pi(0) = vL(-2). All four simulations unexpectedly show that the D-m are ordered for m = 1,..., 9 such that Dm+1 < D-m. Moreover, the D-m squeeze together such that Dm+1/D-m NE arrow 1 as m increases. The values of D-1 lie far above the values of the rest of the D-m, giving rise to a suggestion that a depletion of nonlinearity is occurring which could be the cause of Navier-Stokes regularity. The first simulation is of very anisotropic decaying turbulence; the second and third are of decaying isotropic turbulence from random initial conditions and forced isotropic turbulence at fixed Grashof number respectively; the fourth is of very-high-Reynolds-number forced, stationary, isotropic turbulence at up to resolutions of 4096(3).

Polynomial time and parameterized approximation algorithms for boxicity

The boxicity (cubicity) of a graph G, denoted by box(G) (respectively cub(G)), is the minimum integer k such that G can be represented as the intersection graph of axis parallel boxes (cubes) in ℝ k . The problem of computing boxicity (cubicity) is known to be inapproximable in polynomial time even for graph classes like bipartite, co-bipartite and split graphs, within an O(n 0.5 − ε ) factor for any ε > 0, unless NP = ZPP. We prove that if a graph G on n vertices has a clique on n − k vertices, then box(G) can be computed in time n22O(k2logk) . Using this fact, various FPT approximation algorithms for boxicity are derived. The parameter used is the vertex (or edge) edit distance of the input graph from certain graph families of bounded boxicity - like interval graphs and planar graphs. Using the same fact, we also derive an O(nloglogn√logn√) factor approximation algorithm for computing boxicity, which, to our knowledge, is the first o(n) factor approximation algorithm for the problem. We also present an FPT approximation algorithm for computing the cubicity of graphs, with vertex cover number as the parameter.

Flexibility in Food Extraction Techniques in Urban Free-Ranging Bonnet Macaques, Macaca radiata

Non-human primate populations, other than responding appropriately to naturally occurring challenges, also need to cope with anthropogenic factors such as environmental pollution, resource depletion, and habitat destruction. Populations and individuals are likely to show considerable variations in food extraction abilities, with some populations and individuals more efficient than others at exploiting a set of resources. In this study, we examined among urban free-ranging bonnet macaques, Macaca radiata (a) local differences in food extraction abilities, (b) between-individual variation and within-individual consistency in problem-solving success and the underlying problem-solving characteristics, and (c) behavioral patterns associated with higher efficiency in food extraction. When presented with novel food extraction tasks, the urban macaques having more frequent exposure to novel physical objects in their surroundings, extracted food material from PET bottles and also solved another food extraction task (i.e., extracting an orange from a wire mesh box), more often than those living under more natural conditions. Adults solved the tasks more frequently than juveniles, and females more frequently than males. Both solution-technique and problem-solving characteristics varied across individuals but remained consistent within each individual across the successive presentations of PET bottles. The macaques that solved the tasks showed lesser within-individual variation in their food extraction behavior as compared to those that failed to solve the tasks. A few macaques appropriately modified their problem-solving behavior in accordance with the task requirements and solved the modified versions of the tasks without trial-and-error learning. These observations are ecologically relevant - they demonstrate considerable local differences in food extraction abilities, between-individual variation and within-individual consistency in food extraction techniques among free-ranging bonnet macaques, possibly affecting the species' local adaptability and resilience to environmental changes.

DNA STRUCTURAL FEATURES AND ARCHITECTURE OF PROMOTER REGIONS PLAY A ROLE IN GENE RESPONSIVENESS OF S. CEREVISIAE

Gene expression is the most fundamental biological process, which is essential for phenotypic variation. It is regulated by various external (environment and evolution) and internal (genetic) factors. The level of gene expression depends on promoter architecture, along with other external factors. Presence of sequence motifs, such as transcription factor binding sites (TFBSs) and TATA-box, or DNA methylation in vertebrates has been implicated in the regulation of expression of some genes in eukaryotes, but a large number of genes lack these sequences. On the other hand, several experimental and computational studies have shown that promoter sequences possess some special structural properties, such as low stability, less bendability, low nucleosome occupancy, and more curvature, which are prevalent across all organisms. These structural features may play role in transcription initiation and regulation of gene expression. We have studied the relationship between the structural features of promoter DNA, promoter directionality and gene expression variability in S. cerevisiae. This relationship has been analyzed for seven different measures of gene expression variability, along with two different regulatory effect measures. We find that a few of the variability measures of gene expression are linked to DNA structural properties, nucleosome occupancy, TATA-box presence, and bidirectionality of promoter regions. Interestingly, gene responsiveness is most intimately correlated with DNA structural features and promoter architecture.

Automatic Data Allocation and Buffer Management for Multi-GPU Machines

Multi-GPU machines are being increasingly used in high-performance computing. Each GPU in such a machine has its own memory and does not share the address space either with the host CPU or other GPUs. Hence, applications utilizing multiple GPUs have to manually allocate and manage data on each GPU. Existing works that propose to automate data allocations for GPUs have limitations and inefficiencies in terms of allocation sizes, exploiting reuse, transfer costs, and scalability. We propose a scalable and fully automatic data allocation and buffer management scheme for affine loop nests on multi-GPU machines. We call it the Bounding-Box-based Memory Manager (BBMM). BBMM can perform at runtime, during standard set operations like union, intersection, and difference, finding subset and superset relations on hyperrectangular regions of array data (bounding boxes). It uses these operations along with some compiler assistance to identify, allocate, and manage data required by applications in terms of disjoint bounding boxes. This allows it to (1) allocate exactly or nearly as much data as is required by computations running on each GPU, (2) efficiently track buffer allocations and hence maximize data reuse across tiles and minimize data transfer overhead, and (3) and as a result, maximize utilization of the combined memory on multi-GPU machines. BBMM can work with any choice of parallelizing transformations, computation placement, and scheduling schemes, whether static or dynamic. Experiments run on a four-GPU machine with various scientific programs showed that BBMM reduces data allocations on each GPU by up to 75% compared to current allocation schemes, yields performance of at least 88% of manually written code, and allows excellent weak scaling.

Low-Cost Cloud-Based Design of Smart Rural Energy Device in Microgrid: Perspective India An Energy-On-Demand Service for Rural India

In this paper we present a combination of technologies to provide an Energy-on-Demand (EoD) service to enable low cost innovation suitable for microgrid networks. The system is designed around the low cost and simple Rural Energy Device (RED) Box which in combination with Short Message Service (SMS) communication methodology serves as an elementary proxy for Smart meters which are typically used in urban settings. Further, customer behavior and familiarity in using such devices based on mobile experience has been incorporated into the design philosophy. Customers are incentivized to interact with the system thus providing valuable behavioral and usage data to the Utility Service Provider (USP). Data that is collected over time can be used by the USP for analytics envisioned by using remote computing services known as cloud computing service. Cloud computing allows for a sharing of computational resources at the virtual level across several networks. The customer-system interaction is facilitated by a third party Telecom Service provider (TSP). The approximate cost of the RED Box is envisaged to be under USD 10 on production scale.