New Approximation Algorithms for Minimum Cycle Bases of Graphs

We consider the problem of computing an approximate minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. 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 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 the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. Although in most such applications any cycle basis can be used, a low weight cycle basis often translates to better performance and/or numerical stability. Despite the fact that the problem can be solved exactly in polynomial time, we design approximation algorithms since the performance of the exact algorithms may be too expensive for some practical applications. We present two new algorithms to compute an approximate minimum cycle basis. For any integer k >= 1, we give (2k - 1)-approximation algorithms with expected running time O(kmn(1+2/k) + mn((1+1/k)(omega-1))) and deterministic running time O(n(3+2/k) ), respectively. Here omega is the best exponent of matrix multiplication. It is presently known that omega < 2.376. Both algorithms are o(m(omega)) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Theta(m(omega) ) bound. We also present a 2-approximation algorithm with expected running time O(M-omega root n log n), a linear time 2-approximation algorithm for planar graphs and an O(n(3)) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.

Cytotoxic T lymphocytes raised against Japanese encephalitis virus: effector cell phenotype, target specificity and in vitro virus clearance.

Several H-2 defined cell lines were examined for their ability to support infection and replication of Japanese encephalitis virus (JEV) before their use in in vitro and in vivo stimulation protocols for generating cytotoxic T lymphocytes (CTLs) against JEV. Among II different cell lines tested, two H-2(d) macrophage tumour lines (P388D1, RAW 264.7), an H-2(d) hybridoma (Sp2/0), an H-2K(k)D(d) neuroblastoma (Neuro 2a), and H-2(k) fibroblast cell line (L929) were found to support JEV infection and replication. These cell lines were used to generate anti-JEV CTLs by using in vivo immunization followed by in vitro stimulation of BALB/c mice. We observed that not only syngeneic and allogeneic infected cells but also JEV-infected xenogeneic cells could prime BALB/c mice for the generation of JEV-specific CTLs upon subsequent in vitro stimulation of splenocytes with JEV-infected syngeneic cells. Although infected xenogeneic cells were used for immunization, the anti-JEV effecters that were generated lysed infected syngeneic targets but not JEV-infected xenogeneic or allogeneic target cells in a 5h Cr-51 release assay. These anti-JEV effecters recognized syngeneic target cells infected with West Nile virus to a lesser extent and were shown to be Lyt-2.2(+) T cells. The results of unlabelled cold target competition studies suggested alterations in the cell surface expression of viral antigenic determinants recognized by these CTLs. We further demonstrate that the JEV-specific CTLs generated could virtually block the release of infectious virus particles from infected P388D1 and Neuro 2a cells in vitro.

Additive Spanners and (alpha, beta)-Spanners

An (alpha, beta)-spanner of an unweighted graph G is a subgraph H that distorts distances in G up to a multiplicative factor of a and an additive term beta. It is well known that any graph contains a (multiplicative) (2k - 1, 0)-spanner of size O(n(1+1/k)) and an (additive) (1, 2)-spanner of size O(n(3/2)). However no other additive spanners are known to exist. In this article we develop a couple of new techniques for constructing (alpha, beta)-spanners. Our first result is an additive (1, 6)-spanner of size O(n(4/3)). The construction algorithm can be understood as an economical agent that assigns costs and values to paths in the graph, purchasing affordable paths and ignoring expensive ones, which are intuitively well approximated by paths already purchased. We show that this path buying algorithm can be parameterized in different ways to yield other sparseness-distortion tradeoffs. Our second result addresses the problem of which (alpha, beta)-spanners can be computed efficiently, ideally in linear time. We show that, for any k, a (k, k - 1)-spanner with size O(kn(1+1/k)) can be found in linear time, and, further, that in a distributed network the algorithm terminates in a constant number of rounds. Previous spanner constructions with similar performance had roughly twice the multiplicative distortion.

Conductivity and structural studies on disordered amorphous conducting carbon films

Amorphous carbon films are prepared by the pyrolysis of Tetra Chloro Phthalic Anhydride (TCPA) at different temperatures (700 degrees C to 900 degrees C). DC Conductivity measurements are done on the films in the temperature range 300K to 4.2K. It shows an activated temperature dependence with a small activation energy (0.02eV to 0.003eV). Variable range hopping is observed at low temperatures. The films are characterised by XRD, SEM, TEM, AFM and microRaman. The electronic structure of the film is used to explain the electrical behaviour.

Transport properties, structure, and radiation induced defect studies in amorphous carbon films

Amorphous conducting carbon films are prepared by plasma assisted chemical vapour deposition and their d.c. conductivity (similar to 100 Scm(-1)) is studied from 300K down to 4.2K. The films were irradiated by high energy ion beam(I+13, 170 MeV) with a dose of 10(13) ions/cm(2). As a result a marked decrease in conductivity by two to three orders in magnitude was observed. The structural changes and the defects in the films caused by ion irradiation are studied using photoluminescence, persistent photoconductivity, and ESR spectroscopy.

Japanese encephalitis virus infection of mouse cell lines: ability to prime mice for generation of virus specific cytotoxic T lymphocytes and differences in CTL recognisable viral determinants

Ten different mouse cell lines were examined for Japanese encephalitis virus (JEV) infection in vitro and then tested for their ability to generate virus specific cytotoxic T lymphocytes (CTL). Among all cell lines examined, Neuro La (a neuroblastoma) was readily infected with JEV as examined by immunofluorescence and viral replication. Among other cells, P388D1, RAW 264.7 (Macrophage origin), Sp2/0 (B-cell Hybridoma), YAC-1 (T-cell lymphoma), and L929 (Fibroblast) were semipermissive to JEV infection. The cytopathic effects caused by progressive JEV infection varied from cell line to cell line. In the case of YAC-1 cells long-term viral antigen expression was observed without significant alterations in cell viability. Intermediate degrees of cytopathicity are seen in RAW 264.7 and L929 cells while infection of PS, Neuro 2a, P388D1 and Sp2/0 caused major viability losses. All infected cell lines were able to prime adult BALB/c (H-2(d)) mice for the generation of secondary JEV specific CTL. In contrast to YAC-1, the permissive neuroblastoma cell line Neuro 2a (H-2K(k)D(d)) was found to be least efficient in its ability to stimulate anti-viral CTL generation. Cold target competition studies demonstrated that both Neuro 2a and YAC-1 (H-2K(k)D(d)) cells expressed similar viral determinants that are recognised by CTL, suggesting that the reason for the lower ability of Neuro 2a to stimulate anti-viral CTL was not due to lack of viral CTL determinants. These findings demonstrate that a variety of mouse cell lines can be infected with Japanese encephalitis virus, and that these infected cells could be utilised to generate virus specific CTL in BALB/c mice.

Growth and Characterization of GaAs Epitaxial Layers by MOCVD

technique, on both semi-insulating and semi-conducting CraAs substrates with (100) orientation, offset by 2° towards (110) direction. Systematic variation of As/Ga was performed to gain an understanding of growth process, type of formation and other related physical properties. The films were characterized by using the variety of techniques, such as SEM, EDAX, HRTEM, XRD, and PL. Optical and electrical properties of undoped CyaAs epilayers are presented with reference to the growth conditions and AsH3/TMGa ratio. Photoluminescence measurements of GaAs epilayers were recorded at 4.2K and shows the emission of free exciton and confirmed their high purity. The dominant residual impurities in GaAs are presented by using PL. Finally, electrochemical depth profiling exhibited almost homogeneous background carrier distribution and excellent abruptness between the thin GaAs epilayer and substrate.

Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction

Regenerating codes are a class of distributed storage codes that allow for efficient repair of failed nodes, as compared to traditional erasure codes. An [n, k, d] regenerating code permits the data to be recovered by connecting to any k of the n nodes in the network, while requiring that a failed node be repaired by connecting to any d nodes. The amount of data downloaded for repair is typically much smaller than the size of the source data. Previous constructions of exact-regenerating codes have been confined to the case n = d + 1. In this paper, we present optimal, explicit constructions of (a) Minimum Bandwidth Regenerating (MBR) codes for all values of [n, k, d] and (b) Minimum Storage Regenerating (MSR) codes for all [n, k, d >= 2k - 2], using a new product-matrix framework. The product-matrix framework is also shown to significantly simplify system operation. To the best of our knowledge, these are the first constructions of exact-regenerating codes that allow the number n of nodes in the network, to be chosen independent of the other parameters. The paper also contains a simpler description, in the product-matrix framework, of a previously constructed MSR code with [n = d + 1, k, d >= 2k - 1].

The generalized Onsager model for the secondary flow in a high-speed rotating cylinder

The generalizations of the Onsager model for the radial boundary layer and the Carrier-Maslen model for the end-cap axial boundary layer in a high-speed rotating cylinder are formulated for studying the secondary gas flow due to wall heating and due to insertion of mass, momentum and energy into the cylinder. The generalizations have wider applicability than the original Onsager and Carrier-Maslen models, because they are not restricted to the limit A >> 1, though they are restricted to the limit R e >> 1 and a high-aspect-ratio cylinder whose length/diameter ratio is large. Here, the stratification parameter A = root m Omega(2)R(2)/2k(B)T). This parameter A is the ratio of the peripheral speed, Omega R, to the most probable molecular speed, root 2k(B)T/m, the Reynolds number Re = rho w Omega R(2)/mu, where m is the molecular mass, Omega and R are the rotational speed and radius of the cylinder, k(B) is the Boltzmann constant, T is the gas temperature, rho(w) is the gas density at wall, and mu is the gas viscosity. In the case of wall forcing, analytical solutions are obtained for the sixth-order generalized Onsager equations for the master potential, and for the fourth-order generalized Carrier-Maslen equation for the velocity potential. For the case of mass/momentum/energy insertion into the flow, the separation-of-variables procedure is used, and the appropriate homogeneous boundary conditions are specified so that the linear operators in the axial and radial directions are self-adjoint. The discrete eigenvalues and eigenfunctions of the linear operators (sixth-order and second-order in the radial and axial directions for the Onsager equation, and fourth-order and second-order in the axial and radial directions for the Carrier-Maslen equation) are determined. These solutions are compared with direct simulation Monte Carlo (DSMC) simulations. The comparison reveals that the boundary conditions in the simulations and analysis have to be matched with care. The commonly used `diffuse reflection' boundary conditions at solid walls in DSMC simulations result in a non-zero slip velocity as well as a `temperature slip' (gas temperature at the wall is different from wall temperature). These have to be incorporated in the analysis in order to make quantitative predictions. In the case of mass/momentum/energy sources within the flow, it is necessary to ensure that the homogeneous boundary conditions are accurately satisfied in the simulations. When these precautions are taken, there is excellent agreement between analysis and simulations, to within 10 %, even when the stratification parameter is as low as 0.707, the Reynolds number is as low as 100 and the aspect ratio (length/diameter) of the cylinder is as low as 2, and the secondary flow velocity is as high as 0.2 times the maximum base flow velocity. The predictions of the generalized models are also significantly better than those of the original Onsager and Carrier-Maslen models, which are restricted to thin boundary layers in the limit of high stratification parameter.

Effect of bismuth doping in GeSe and GeSeTe glasses by photoluminescence spectroscopy

Semiconducting chalcogenide glasses in the systems GeSe and GeSeTe with the addition of bismuth show unusual phenomena of p - to - n transition. Samples for characterization were prepared in bulk form by melt-quenching technique, with increasing Bi at. % to replace selenium. Photoluminescence (PL) spectroscopic studies on all the samples were carried out at 4.2K using an Ar-Ion laser for illuminating the samples. The laser power used was 200mw. Both the systems show a decrease in the intensity of PL signal with increasing Bi content. This interesting behavior is discussed on the basis of a charged defect model for chalcogenide glasses, proposed by Mott, Davis and Street (MDS). The effect of bismuth addition on these charged defects is also discussed to explain the carrier type reversal.

Interference Alignment in Regenerating Codes for Distributed Storage: Necessity and Code Constructions

Regenerating codes are a class of recently developed codes for distributed storage that, like Reed-Solomon codes, permit data recovery from any arbitrary of nodes. However regenerating codes possess in addition, the ability to repair a failed node by connecting to any arbitrary nodes and downloading an amount of data that is typically far less than the size of the data file. This amount of download is termed the repair bandwidth. Minimum storage regenerating (MSR) codes are a subclass of regenerating codes that require the least amount of network storage; every such code is a maximum distance separable (MDS) code. Further, when a replacement node stores data identical to that in the failed node, the repair is termed as exact. The four principal results of the paper are (a) the explicit construction of a class of MDS codes for d = n - 1 >= 2k - 1 termed the MISER code, that achieves the cut-set bound on the repair bandwidth for the exact repair of systematic nodes, (b) proof of the necessity of interference alignment in exact-repair MSR codes, (c) a proof showing the impossibility of constructing linear, exact-repair MSR codes for d < 2k - 3 in the absence of symbol extension, and (d) the construction, also explicit, of high-rate MSR codes for d = k+1. Interference alignment (IA) is a theme that runs throughout the paper: the MISER code is built on the principles of IA and IA is also a crucial component to the nonexistence proof for d < 2k - 3. To the best of our knowledge, the constructions presented in this paper are the first explicit constructions of regenerating codes that achieve the cut-set bound.

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).

On k-stellated and k-stacked spheres

We introduce the class Sigma(k)(d) of k-stellated (combinatorial) spheres of dimension d (0 <= k <= d + 1) and compare and contrast it with the class S-k(d) (0 <= k <= d) of k-stacked homology d-spheres. We have E-1(d) = S-1(d), and Sigma(k)(d) subset of S-k(d) ford >= 2k-1. However, for each k >= 2 there are k-stacked spheres which are not k-stellated. For d <= 2k - 2, the existence of k-stellated spheres which are not k-stacked remains an open question. We also consider the class W-k(d) (and K-k(d)) of simplicial complexes all whose vertex-links belong to Sigma(k)(d - 1) (respectively, S-k(d - 1)). Thus, W-k(d) subset of K-k(d) for d >= 2k, while W-1(d) = K-1(d). Let (K) over bar (k)(d) denote the class of d-dimensional complexes all whose vertex-links are k-stacked balls. We show that for d >= 2k + 2, there is a natural bijection M -> (M) over bar from K-k(d) onto (K) over bar (k)(d + 1) which is the inverse to the boundary map partial derivative: (K) over bar (k)(d + 1) -> (K) over bar (k)(d). Finally, we complement the tightness results of our recent paper, Bagchi and Datta (2013) 5], by showing that, for any field F, an F-orientable (k + 1)-neighbourly member of W-k(2k + 1) is F-tight if and only if it is k-stacked.

Solving MIN ONES 2-SAT as fast as VERTEX COVER

The problem of finding a satisfying assignment that minimizes the number of variables that are set to 1 is NP-complete even for a satisfiable 2-SAT formula. We call this problem MIN ONES 2-SAT. It generalizes the well-studied problem of finding the smallest vertex cover of a graph, which can be modeled using a 2-SAT formula with no negative literals. The natural parameterized version of the problem asks for a satisfying assignment of weight at most k. In this paper, we present a polynomial-time reduction from MIN ONES 2-SAT to VERTEX COVER without increasing the parameter and ensuring that the number of vertices in the reduced instance is equal to the number of variables of the input formula. Consequently, we conclude that this problem also has a simple 2-approximation algorithm and a 2k - c logk-variable kernel subsuming (or, in the case of kernels, improving) the results known earlier. Further, the problem admits algorithms for the parameterized and optimization versions whose runtimes will always match the runtimes of the best-known algorithms for the corresponding versions of vertex cover. Finally we show that the optimum value of the LP relaxation of the MIN ONES 2-SAT and that of the corresponding VERTEX COVER are the same. This implies that the (recent) results of VERTEX COVER version parameterized above the optimum value of the LP relaxation of VERTEX COVER carry over to the MIN ONES 2-SAT version parameterized above the optimum of the LP relaxation of MIN ONES 2-SAT. (C) 2013 Elsevier B.V. All rights reserved.

ON POLYTOPAL UPPER BOUND SPHERES

Generalizing a result (the case k = 1) due to M. A. Perles, we show that any polytopal upper bound sphere of odd dimension 2k + 1 belongs to the generalized Walkup class K-k(2k + 1), i.e., all its vertex links are k-stacked spheres. This is surprising since it is far from obvious that the vertex links of polytopal upper bound spheres should have any special combinatorial structure. It has been conjectured that for d not equal 2k + 1, all (k + 1)-neighborly members of the class K-k(d) are tight. The result of this paper shows that the hypothesis d not equal 2k + 1 is essential for every value of k >= 1.