A constant factor approximation algorithm for boxicity of circular arc graphs

The boxicity (resp. cubicity) of a graph G(V, E) is the minimum integer k such that G can be represented as the intersection graph of axis parallel boxes (resp. cubes) in R-k. Equivalently, it is the minimum number of interval graphs (resp. unit interval graphs) on the vertex set V, such that the intersection of their edge sets is E. The problem of computing boxicity (resp. cubicity) is known to be inapproximable, even for restricted graph classes like bipartite, co-bipartite and split graphs, within an O(n(1-epsilon))-factor for any epsilon > 0 in polynomial time, unless NP = ZPP. For any well known graph class of unbounded boxicity, there is no known approximation algorithm that gives n(1-epsilon)-factor approximation algorithm for computing boxicity in polynomial time, for any epsilon > 0. In this paper, we consider the problem of approximating the boxicity (cubicity) of circular arc graphs intersection graphs of arcs of a circle. Circular arc graphs are known to have unbounded boxicity, which could be as large as Omega(n). We give a (2 + 1/k) -factor (resp. (2 + log n]/k)-factor) polynomial time approximation algorithm for computing the boxicity (resp. cubicity) of any circular arc graph, where k >= 1 is the value of the optimum solution. For normal circular arc (NCA) graphs, with an NCA model given, this can be improved to an additive two approximation algorithm. The time complexity of the algorithms to approximately compute the boxicity (resp. cubicity) is O(mn + n(2)) in both these cases, and in O(mn + kn(2)) = O(n(3)) time we also get their corresponding box (resp. cube) representations, where n is the number of vertices of the graph and m is its number of edges. Our additive two approximation algorithm directly works for any proper circular arc graph, since their NCA models can be computed in polynomial time. (C) 2014 Elsevier B.V. All rights reserved.

Depalladation of Neutral Monoalkyne- and Dialkyne-Inserted Palladacycles and Alkyne Insertion/Depalladation Reactions of Cationic Palladacycles Derived from N,N `,N `'-Triarylguanidines as Facile Routes for Guanidine-Containing Heterocycles/Carbocycles: Synthetic, Structural, and Mechanistic Aspects

Depalladation of the monoalkyne-inserted cyclopalldated guanidines (kappa 2(C,N)Pd(2,6-Me2C5H3N)Br] (I and II) in PhCl under reflux conditions and that of the dialkyne-inserted cyclopalladated guanidine kappa(2)(C,N):eta(2)(C=C)PdBr] (III) in pyridine under reflux conditions afforded a guanidine-containing indole (1), imidaziondole (2), and benzazepine (3) in 80%, 67%, and 76%, yields, respectively. trans-L2PdBr2] species (L = 2,6-Me2C5H3N, C5H5N) were also isolated in the aforementioned reactions in 35%, 42%, and 40% yields. Further , the reaction of the cyclopalladated guanidine kappa(2)(C,N)Pd(mu-Br)](2) (IV) with AgBF4 in a CH2Cl2/MeCN mixture afforded the cationic pincer type cyclopalladated guanidine kappa(3)(C,N,O)Pd(MeCN)]BF4] (4) in 85% yield and this palladacycle upon crystallization in MeCN and the reaction of kappa(2)(C,N)Pd(mu-Br)](2) (V) with AgBf(4) in a CH2Cl2/MeCN mixture afforded the cationic palladacycles {kappa(2)(C,N)Pd(MeCN)(2)]BF4](5 and 6) in 89% and 91% yields, respectively. The separate reactions of 4 with 2 equiv of methyl phenylpropiolate (MPP) or diphenylacetylene (DPA) and the reaction of 5 with 2 equiv of MPP in PhCl at 110 degrees C afforded the guanidine-containing quinazolinium tetrafluoroborate 7 in 25-32% yields. The reaction of 6 with 2 equiv of DPA under otherwise identical conditions afforded the unsymmetrically substituted guanidinium tetrafluoroborate 8, containing a highly substituted naphthalene unit, in 82% yield. Compounds 1-8 were characterized by analytical and spectroscopic techniques, and all compounds except 4 were characterized by single-crystal X-ray diffraction. The Molecular structure of 2 and 3 are nove, as the framework in the former arises due to the formation of two C-N bonds upon depalladation while the butadienyl unit in the latter revealed cis,cis stereochemistry, a-feature unprecedented in alkyne insertion chemistry. Plausible pathways for the formation of heterocycles/carbocycles are proposed. the influence of substitutents on the aryl rings fo the cyclopalladated guanidine moiety and those on alkynes upon the nature of the products in addressed. Heterocycles 1 and 7 revealed the presence of two rotamers in about a 1.00:0.43 ratio in CDCl3 and in about a 1.00:0.14 ratio in CD3OD, respectively, as detected by H-1 NMR spectroscopy while in CD3CN and DMSO-d(6) (1) and CD3CN and CDCl3 (7), these heterocycles revealed the presence of a single rotamer. These spectral features are attributed to the restricted C-N single-bond rotation of the CN3 unit of the guanidine moiety, which possibly arises from steric constraint due to the formation of a N-H center dot center dot center dot Cl hydrogen bond with CDCl3 (1) and N-H center dot center dot center dot O and O-D center dot center dot center dot O hydrogen bonds with CD3OD (7).

Vertex Cover Gets Faster and Harder on Low Degree Graphs

The problem of finding an optimal vertex cover in a graph is a classic NP-complete problem, and is a special case of the hitting set question. On the other hand, the hitting set problem, when asked in the context of induced geometric objects, often turns out to be exactly the vertex cover problem on restricted classes of graphs. In this work we explore a particular instance of such a phenomenon. We consider the problem of hitting all axis-parallel slabs induced by a point set P, and show that it is equivalent to the problem of finding a vertex cover on a graph whose edge set is the union of two Hamiltonian Paths. We show the latter problem to be NP-complete, and also give an algorithm to find a vertex cover of size at most k, on graphs of maximum degree four, whose running time is 1.2637(k) n(O(1)).

Hydrophobic hydration driven self-assembly of curcumin in water: Similarities to nucleation and growth under large metastability, and an analysis of water dynamics at heterogeneous surfaces

As the beneficial effects of curcumin have often been reported to be limited to its small concentrations, we have undertaken a study to find the aggregation properties of curcumin in water by varying the number of monomers. Our molecular dynamics simulation results show that the equilibrated structure is always an aggregated state with remarkable structural rearrangements as we vary the number of curcumin monomers from 4 to 16 monomers. We find that the curcumin monomers form clusters in a very definite pattern where they tend to aggregate both in parallel and anti-parallel orientation of the phenyl rings, often seen in the formation of beta-sheet in proteins. A considerable enhancement in the population of parallel alignments is observed with increasing the system size from 12 to 16 curcumin monomers. Due to the prevalence of such parallel alignment for large system size, a more closely packed cluster is formed with maximum number of hydrophobic contacts. We also follow the pathway of cluster growth, in particular the transition from the initial segregated to the final aggregated state. We find the existence of a metastable structural intermediate involving a number of intermediate-sized clusters dispersed in the solution. We have constructed a free energy landscape of aggregation where the metatsable state has been identified. The course of aggregation bears similarity to nucleation and growth in highly metastable state. The final aggregated form remains stable with the total exclusion of water from its sequestered hydrophobic core. We also investigate water structure near the cluster surface along with their orientation. We find that water molecules form a distorted tetrahedral geometry in the 1st solvation layer of the cluster, interacting rather strongly with the hydrophilic groups at the surface of the curcumin. The dynamics of such quasi-bound water molecules near the surface of curcumin cluster is considerably slower than the bulk signifying a restricted motion as often found in protein hydration layer. (C) 2014 AIP Publishing LLC.

An iterative framework for sparse signal reconstruction algorithms

It has been shown that iterative re-weighted strategies will often improve the performance of many sparse reconstruction algorithms. However, these strategies are algorithm dependent and cannot be easily extended for an arbitrary sparse reconstruction algorithm. In this paper, we propose a general iterative framework and a novel algorithm which iteratively enhance the performance of any given arbitrary sparse reconstruction algorithm. We theoretically analyze the proposed method using restricted isometry property and derive sufficient conditions for convergence and performance improvement. We also evaluate the performance of the proposed method using numerical experiments with both synthetic and real-world data. (C) 2014 Elsevier B.V. All rights reserved.

Optimal control of grinding mill circuit using model predictive static programming: A new nonlinear MPC paradigm

The recently developed reference-command tracking version of model predictive static programming (MPSP) is successfully applied to a single-stage closed grinding mill circuit. MPSP is an innovative optimal control technique that combines the philosophies of model predictive control (MPC) and approximate dynamic programming. The performance of the proposed MPSP control technique, which can be viewed as a `new paradigm' under the nonlinear MPC philosophy, is compared to the performance of a standard nonlinear MPC technique applied to the same plant for the same conditions. Results show that the MPSP control technique is more than capable of tracking the desired set-point in the presence of model-plant mismatch, disturbances and measurement noise. The performance of MPSP and nonlinear MPC compare very well, with definite advantages offered by MPSP. The computational speed of MPSP is increased through a sequence of innovations such as the conversion of the dynamic optimization problem to a low-dimensional static optimization problem, the recursive computation of sensitivity matrices and using a closed form expression to update the control. To alleviate the burden on the optimization procedure in standard MPC, the control horizon is normally restricted. However, in the MPSP technique the control horizon is extended to the prediction horizon with a minor increase in the computational time. Furthermore, the MPSP technique generally takes only a couple of iterations to converge, even when input constraints are applied. Therefore, MPSP can be regarded as a potential candidate for online applications of the nonlinear MPC philosophy to real-world industrial process plants. (C) 2014 Elsevier Ltd. All rights reserved.

Phytoplankton size structure in the southern Bay of Bengal modified by the Summer Monsoon Current and associated eddies: Implications on the vertical biogenic flux

The present study combines field and satellite observations to investigate how hydrographical transformations influence phytoplankton size structure in the southern Bay of Bengal during the peak Southwest Monsoon/Summer Monsoon (July-August). The intrusion of the Summer Monsoon Current (SMC) into the Bay of Bengal and associated changes in sea surface chemistry, traceable eastward up to 90 degrees E along 8 degrees N, seems to influence biology of the region significantly. Both in situ and satellite (MODIS) data revealed low surface chlorophyll except in the area influenced by the SMC During the study period, two well-developed cydonic eddies (north) and an anti-cyclonic eddy (south), closely linked to the main eastward flow of the SMC, were sampled. Considering the capping effect of the low-saline surface water that is characteristic of the Bay of Bengal, the impact of the cyclonic eddy, estimated in terms of enhanced nutrients and chlorophyll, was mostly restricted to the subsurface waters (below 20 m depth). Conversely, the anti-cyclonic eddy aided by the SMC was characterized by considerably higher nutrient concentration and chlorophyll in the upper water column (upper 60 m), which was contrary to the general characteristic of such eddies. Albeit smaller phytoplankton predominated the southern Bay of Bengal (60-95% of the total chlorophyll), the contribution of large phytoplankton was double in the regions influenced by the SMC and associated eddies. Multivariate analysis revealed the extent to which SMC-associated eddies spatially influence phytoplankton community structure. The study presents the first direct quantification of the size structure of phytoplankton from the southern Bay of Bengal and demonstrates that the SMC-associated hydrographical ramifications significantly increase the phytoplankton biomass contributed by larger phytoplankton and thereby influence the vertical opal and organic carbon flux in the region. (C) 2014 Elsevier B.V. All rights reserved.

On the Communication Complexity of Secret Key Generation in the Multiterminal Source Model

Communication complexity refers to the minimum rate of public communication required for generating a maximal-rate secret key (SK) in the multiterminal source model of Csiszar and Narayan. Tyagi recently characterized this communication complexity for a two-terminal system. We extend the ideas in Tyagi's work to derive a lower bound on communication complexity in the general multiterminal setting. In the important special case of the complete graph pairwise independent network (PIN) model, our bound allows us to determine the exact linear communication complexity, i.e., the communication complexity when the communication and SK are restricted to be linear functions of the randomness available at the terminals.

Low frequency modulation of jets in quasigeostrophic turbulence

Quasigeostrophic turbulence on a beta-plane with a finite deformation radius is studied numerically, with particular emphasis on frequency and combined wavenumber-frequency domain analyses. Under suitable conditions, simulations with small-scale random forcing and large-scale drag exhibit a spontaneous formation of multiple zonal jets. The first hint of wave-like features is seen in the distribution of kinetic energy as a function of frequency; specifically, for progressively larger deformation scales, there are systematic departures in the form of isolated peaks (at progressively higher frequencies) from a power-law scaling. Concomitantly, there is an inverse flux of kinetic energy in frequency space which extends to lower frequencies for smaller deformation scales. The identification of these peaks as Rossby waves is made possible by examining the energy spectrum in frequency-zonal wavenumber and frequency-meridional wavenumber diagrams. In fact, the modified Rhines scale turns out to be a useful measure of the dominant meridional wavenumber of the modulating Rossby waves; once this is fixed, apart from a spectral peak at the origin (the steady jet), almost all the energy is contained in westward propagating disturbances that follow the theoretical Rossby dispersion relation. Quite consistently, noting that the zonal scale of the modulating waves is restricted to the first few wavenumbers, the energy spectrum is almost entirely contained within the corresponding Rossby dispersion curves on a frequency-meridional wavenumber diagram. Cases when jets do not form are also considered; once again, there is a hint of Rossby wave activity, though the spectral peaks are quite muted. Further, the kinetic energy scaling in frequency domain follows a -5/3 power-law and is distributed much more broadly in frequency-wavenumber diagrams. (C) 2015 AIP Publishing LLC.

Excited electronic state decomposition mechanisms of clusters of dimethylnitramine and aluminum

In this report, electronically non-adiabatic decomposition pathways of clusters of dimethylnitramine and aluminum (DMNA-Al and DMNA-Al-2) are discussed in comparison to isolated dimethylnitramine (DMNA). Electronically excited state processes of DMNA-Al and DMNA-Al-2 are explored using the complete active space self-consistent field (CASSCF) and the restricted active space self-consistent field (RASSCF) theories, respectively. Similar to the nitro-nitrite isomerization reaction pathway of DMNA, DMNA-Al-n clusters also exhibit isomerization pathway. However, it involves several other steps, such as, first Al-O bond dissociation, then N-N bond dissociation followed by isomerization and finally NO elimination. Furthermore, DMNA-Al-n clusters exhibit overall exothermic decomposition reaction pathway and isolated DMNA shows overall endothermic reaction channel.

A matrix model for QCD: QCD color is mixed

We use general arguments to show that colored QCD states when restricted to gauge invariant local observables are mixed. This result has important implications for confinement: a pure colorless state can never evolve into two colored states by unitary evolution. Furthermore, the mean energy in such a mixed colored state is infinite. Our arguments are confirmed in a matrix model for QCD that we have developed using the work of Narasimhan and Ramadas(3) and Singer.(2) This model, a (0 + 1)-dimensional quantum mechanical model for gluons free of divergences and capturing important topological aspects of QCD, is adapted to analytical and numerical work. It is also suitable to work on large N QCD. As applications, we show that the gluon spectrum is gapped and also estimate some low-lying levels for N = 2 and 3 (colors). Incidentally the considerations here are generic and apply to any non-Abelian gauge theory.

Intermetallic eutectic alloys in the Ni-Al-Zr system with attractive high temperature properties

We describe a group of alloys with ultrahigh strength of about 2 GPa at 700 degrees C and exceptional oxidation resistance to 1100 degrees C. These alloys exploit intermetallic phases with stable oxide forming elements that combine to form fine nanometric scale structures through eutectic transformations in ternary systems. The alloys offer engineering tensile plasticity of about 4% at room temperature though both conventional dislocation mechanisms and twinning in the more complex intermetallic constituent, along with slip lengths that are restricted by the interphase boundaries in the eutectics.

Unusual Fragility and Cooperativity in Glass-Forming and Crystalline PVDF/PMMA Blends in the Presence of Multiwall Carbon Nanotubes

Poly(vinylidene fluoride) (PVDF) and poly(methyl methacrylate) (PMMA) are completely miscible below 50 wt % PVDF in the blends. In this work, an attempt was made to understand the fragility/cooperativity relation in glass-forming and crystalline blends of PVDF/PMMA and in the presence of a heteronucleating agent, multiwall carbon nanotubes (CNTs). Hence, three representative blends were chosen: a completely amorphous (10/90 by wt, PVDF/PMMA), on the verge of amorphous miscibility (50/50 by wt, PVDF/PMMA), and crystalline (60/40 by wt, PVDF/PMMA) blends. The intermolecular cooperativity/coupling, fragility, and configurational entropy near the glass transition temperature (T-g) were studied using differential scanning calorimetry (DSC) and broadband dielectric relaxation spectroscopy (DRS). It was observed that the blends with higher concentration of PMMA were more fragile (fragility index m = 141) and those with higher concentration of PVDF were more strong (m = 78). Interestingly, the coupling was less in the glass-forming blends (10/90 by wt, PVDF/PMMA) than the crystalline blends as manifested from DRS. This observation was also supported by DSC measurements which reflected that the cooperative rearranging region (CRR) existed over a smaller length scales in fragile blends as compared to strong blends, possibly due to restricted amorphous mobility. This effect was more prominent in the presence of CNTs, in particular for 50/50 (by wt) and 60/40 (by wt) PVDF/PMMA blends. Further, the configurational entropy, as manifested from DRS, decreased significantly in the strong blends in striking contrast to the fragile blends, supported by DSC, which manifested in an increase in the volume of cooperativity in the strong blends. The higher coupling in the crystalline blends can be attributed to good packing of the amorphous regions. While this is understood for crystalline blends (60/40 by wt, PVDF/PMMA), it is envisaged that enhanced dynamic heterogeneity is accountable for increased coupling in the case of blends which are on the verge of amorphous miscibility (50/50 by wt, PVDF/PMMA). The latter is also supported by broad relaxations near the T-g in DRS. Interestingly, the intermolecular coupling in the blends in the presence of CNTs has reduced, though the potential energy barrier hindering the rearrangement of CRR is lower than the blends without CNTs. In addition, the amorphous packing is not as effective as the blends without CNTs. This is manifested from reduced volume of cooperativity in particular, for 50/50 (by wt) and 60/40 (by wt) blends.

On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties

We study the problem of finding small s-t separators that induce graphs having certain properties. It is known that finding a minimum clique s-t separator is polynomial-time solvable (Tarjan in Discrete Math. 55:221-232, 1985), while for example the problems of finding a minimum s-t separator that induces a connected graph or forms an independent set are fixed-parameter tractable when parameterized by the size of the separator (Marx et al. in ACM Trans. Algorithms 9(4): 30, 2013). Motivated by these results, we study properties that generalize cliques, independent sets, and connected graphs, and determine the complexity of finding separators satisfying these properties. We investigate these problems also on bounded-degree graphs. Our results are as follows: Finding a minimum c-connected s-t separator is FPT for c=2 and W1]-hard for any ca parts per thousand yen3. Finding a minimum s-t separator with diameter at most d is W1]-hard for any da parts per thousand yen2. Finding a minimum r-regular s-t separator is W1]-hard for any ra parts per thousand yen1. For any decidable graph property, finding a minimum s-t separator with this property is FPT parameterized jointly by the size of the separator and the maximum degree. Finding a connected s-t separator of minimum size does not have a polynomial kernel, even when restricted to graphs of maximum degree at most 3, unless .

Invisible decays of the heavier Higgs boson in the minimal supersymmetric standard model

We consider the possibility that the heavier CP-even Higgs boson (H-0) in the minimal supersymmetric standard model (MSSM) decays invisibly into neutralinos in the light of the recent discovery of the 126 GeV resonance at the CERN Large Hadron Collider (LHC). For this purpose we consider the minimal supersymmetric standard model with universal, nonuniversal and arbitrary boundary conditions on the supersymmetry breaking gaugino mass parameters at the grand unified scale. Typically, scenarios with universal and nonuniversal gaugino masses do not allow invisible decays of the lightest Higgs boson (h(0)), which is identified with the 126 GeV resonance, into the lightest neutralinos in the MSSM. With arbitrary gaugino masses at the grand unified scale, such an invisible decay is possible. The second lightest Higgs boson can decay into various invisible final states for a considerable region of the MSSM parameter space with arbitrary gaugino masses as well as with the gaugino masses restricted by universal and nonuniversal boundary conditions at the grand unified scale. The possibility of the second lightest Higgs boson of the MSSM decaying into invisible channels is more likely for arbitrary gaugino masses at the grand unified scale. The heavier Higgs boson decay into lighter particles leads to the intriguing possibility that the entire Higgs boson spectrum of the MSSM may be visible at the LHC even if it decays invisibly, during the searches for an extended Higgs boson sector at the LHC. In such a scenario the nonobservation of the extended Higgs sector of the MSSM may carefully be used to rule out regions of the MSSM parameter space at the LHC.