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

Time resolved terahertz spectroscopy of low frequency electronic resonances and optical pump-induced terahertz photoconductivity in reduced graphene oxide membrane

Towards ultrafast optoelectronic applications of single and a few layer reduced graphene oxide (RGO), we study time domain terahertz spectroscopy and optical pump induced changes in terahertz conductivity of self-supported RGO membrane in the spectral window of 0.5-3.5 THz. The real and imaginary parts of conductivity spectra clearly reveal low frequency resonances, attributed to the energy gaps due to the van Hove singularities in the density of states flanking the Dirac points arising due to the relative rotation of the graphene layers. Further, optical pump induced terahertz conductivity is positive, pointing to the dominance of intraband scattering processes. The relaxation dynamics of the photo-excited carriers consists of three cooling pathways: the faster (similar to 450 fs) one due to optical phonon emission followed by disorder mediated large momentum and large energy acoustic phonon emission with a time constant of a few ps (called the super-collision mechanism) and a very large time (similar to 100 ps) arising from the deep trap states. The frequency dependence of the dynamic conductivity at different delay times is analyzed in term of Drude-Smith model. (C) 2014 Published by Elsevier Ltd.

Porous wide band gap BiNbO4 ceramic nanopowder synthesised by low temperature solution-based method for gas sensing applications

In this study, we report the gas sensing behavior of BiNbO4 nanopowder prepared by a low temperature simple solution-based method. Before the sensing behaviour study, the as-synthesized nanopowder was characterized by X-ray diffraction, scanning electron microscopy, transmission electron microscopy, UV-diffuse reflectance spectroscopy, impedance analysis, and surface area measurement. The NH3 sensing behavior of BiNbO4 was then studied by temperature modulation (50-350 degrees C) as well as concentration modulation (20-140 ppm). At the optimum operating temperature of 325 degrees C, the sensitivity was measured to be 90%. The cross-sensitivity of as-synthesized BiNbO4 sensor was also investigated by assessing the sensing behavior toward other gases such as hydrogen sulphide (H2S), ethanol (C2H5OH), and liquid petroleum gas (LPG). Finally, selectivity of the sensing material toward NH3 was characterized by observing the sensor response with gas concentrations in the range 20-140 ppm. The response and recovery time for NH3 sensing at 120 ppm were about 16 s and about 17 s, respectively.

Low temperature magnetoresistance and magnetization studies of iron encapsulated multiwall carbon nanotube/polyvinyl chloride composites

We present the experimental results of temperature dependent magnetoresistance (MR) and the magnetization studies of iron encapsulated multiwall carbon nanotube (MWCNT)/polyvinyl chloride (PVC) composites with different wt% of MWCNTs. Transmission electron microscopy characterization shows that MWCNTs are encapsulated with rod-shaped iron nanoparticles of aspect ratio of similar to 3. The MR behavior of 1.9 wt% MWCNT/PVC sample shows dominance of forward scattering and wave function shrinkage whereas, weak localization and electron-electron interactions explain the MR data of higher wt% samples (9.1, 16.6 and 44.4 wt%). The composites of 4.7 and 9.1 wt% exhibit ferromagnetic behavior at all temperatures with room temperature coercivities of similar to 1036 and 628 Oe, respectively. (C) 2014 Elsevier Ltd. All rights reserved.