Boxicity of Circular Arc Graphs

A k-dimensional box is a Cartesian product R(1)x...xR(k) where each R(i) is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-dimensional boxes. That is, two vertices are adjacent if and only if their corresponding boxes intersect. A circular arc graph is a graph that can be represented as the intersection graph of arcs on a circle. We show that if G is a circular arc graph which admits a circular arc representation in which no arc has length at least pi(alpha-1/alpha) for some alpha is an element of N(>= 2), then box(G) <= alpha (Here the arcs are considered with respect to a unit circle). From this result we show that if G has maximum degree Delta < [n(alpha-1)/2 alpha] for some alpha is an element of N(>= 2), then box(G) <= alpha. We also demonstrate a graph having box(G) > alpha but with Delta = n (alpha-1)/2 alpha + n/2 alpha(alpha+1) + (alpha+2). For a proper circular arc graph G, we show that if Delta < [n(alpha-1)/alpha] for some alpha is an element of N(>= 2), then box(G) <= alpha. Let r be the cardinality of the minimum overlap set, i.e. the minimum number of arcs passing through any point on the circle, with respect to some circular arc representation of G. We show that for any circular arc graph G, box(G) <= r + 1 and this bound is tight. We show that if G admits a circular arc representation in which no family of k <= 3 arcs covers the circle, then box(G) <= 3 and if G admits a circular arc representation in which no family of k <= 4 arcs covers the circle, then box(G) <= 2. We also show that both these bounds are tight.

Effect of pairing fluctuations on low-energy electronic spectra in cuprate superconductors

We describe here a minimal theory of tight-binding electrons moving on the square planar Cu lattice of the hole-doped cuprates and mixed quantum mechanically with their own Cooper pairs. The superconductivity occurring at the transition temperature T(c) is the long-range, d-wave symmetry phase coherence of these Cooper pairs. Fluctuations, necessarily associated with incipient long-range superconducting order, have a generic large-distance behavior near T(c). We calculate the spectral density of electrons coupled to such Cooper-pair fluctuations and show that features observed in angle resolved photoemission spectroscopy (ARPES) experiments on different cuprates above T(c) as a function of doping and temperature emerge naturally in this description. These include ``Fermi arcs'' with temperature-dependent length and an antinodal pseudogap, which fills up linearly as the temperature increases toward the pseudogap temperature. Our results agree quantitatively with experiment. Below T(c), the effects of nonzero superfluid density and thermal fluctuations are calculated and compared successfully with some recent ARPES experiments, especially the observed bending or deviation of the superconducting gap from the canonical d-wave form.

Output-Sensitive Construction of Reeb Graphs

The Reeb graph of a scalar function represents the evolution of the topology of its level sets. This paper describes a near-optimal output-sensitive algorithm for computing the Reeb graph of scalar functions defined over manifolds or non-manifolds in any dimension. Key to the simplicity and efficiency of the algorithm is an alternate definition of the Reeb graph that considers equivalence classes of level sets instead of individual level sets. The algorithm works in two steps. The first step locates all critical points of the function in the domain. Critical points correspond to nodes in the Reeb graph. Arcs connecting the nodes are computed in the second step by a simple search procedure that works on a small subset of the domain that corresponds to a pair of critical points. The paper also describes a scheme for controlled simplification of the Reeb graph and two different graph layout schemes that help in the effective presentation of Reeb graphs for visual analysis of scalar fields. Finally, the Reeb graph is employed in four different applications-surface segmentation, spatially-aware transfer function design, visualization of interval volumes, and interactive exploration of time-varying data.

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.

GINZBURG-LANDAU LIKE THEORY OF HIGH TEMPERATURE SUPERCONDUCTIVITY IN THE CUPRATES: EMERGENT d-WAVE ORDER

High temperature superconductivity in the cuprates remains one of the most widely investigated, constantly surprising and poorly understood phenomena in physics. Here, we describe briefly a new phenomenological theory inspired by the celebrated description of superconductivity due to Ginzburg and Landau and believed to describe its essence. This posits a free energy functional for the superconductor in terms of a complex order parameter characterizing it. We propose that there is, for superconducting cuprates, a similar functional of the complex, in plane, nearest neighbor spin singlet bond (or Cooper) pair amplitude psi(ij). Further, we suggest that a crucial part of it is a (short range) positive interaction between nearest neighbor bond pairs, of strength J'. Such an interaction leads to nonzero long wavelength phase stiffness or superconductive long range order, with the observed d-wave symmetry, below a temperature T-c similar to zJ' where z is the number of nearest neighbors; d-wave superconductivity is thus an emergent, collective consequence. Using the functional, we calculate a large range of properties, e. g., the pseudogap transition temperature T* as a function of hole doping x, the transition curve T-c(x), the superfluid stiffness rho(s)(x, T), the specific heat (without and with a magnetic field) due to the fluctuating pair degrees of freedom and the zero temperature vortex structure. We find remarkable agreement with experiment. We also calculate the self-energy of electrons hopping on the square cuprate lattice and coupled to electrons of nearly opposite momenta via inevitable long wavelength Cooper pair fluctuations formed of these electrons. The ensuing results for electron spectral density are successfully compared with recent experimental results for angle resolved photo emission spectroscopy (ARPES), and comprehensively explain strange features such as temperature dependent Fermi arcs above T-c and the ``bending'' of the superconducting gap below T-c.

Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance

We present two online algorithms for maintaining a topological order of a directed n-vertex acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm handles m arc additions in O(m(3/2)) time. For sparse graphs (m/n = O(1)), this bound improves the best previous bound by a logarithmic factor, and is tight to within a constant factor among algorithms satisfying a natural locality property. Our second algorithm handles an arbitrary sequence of arc additions in O(n(5/2)) time. For sufficiently dense graphs, this bound improves the best previous bound by a polynomial factor. Our bound may be far from tight: we show that the algorithm can take Omega(n(2)2 root(2lgn)) time by relating its performance to a generalization of the k-levels problem of combinatorial geometry. A completely different algorithm running in Theta (n(2) log n) time was given recently by Bender, Fineman, and Gilbert. We extend both of our algorithms to the maintenance of strong components, without affecting the asymptotic time bounds.

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.

Microscopic and dielectric studies of ZnO nanoparticles loaded in ortho-chloropolyaniline nanocomposites

We have studied the preparation of zinc oxide nanoparticles loaded in various weight percentages in ortho-chloropolyaniline by in situ polymerization method. The length of the O-chloropolyaniline tube is found to be 200 nm and diameter is about 150 nm wherein the embedded ZnO nanoparticles is of 13 nm as confirmed from scanning electron microscopy as well as transmission electron microscopy characterizations. The presence of the vibration band of the metal oxide and other characteristic bands confirms that the polymer nanocomposites are characterized by their Fourier transmission infrared spectroscopy. The X-ray diffraction pattern of nanocomposites reveals their polycrystalline nature. Electrical property of nanocomposites is a function of the filler as well as the matrix. Cole-Cole plots reveal the presence of well-defined semicircular arcs at high frequencies which are attributed to the bulk resistance of the material. Among all nanocomposites, 30 wt% shows the low relaxation time of 151 s, and hence it has high conductivity.

Role of substrate temperature on the properties of Na-doped ZnO thin film nanorods and performance of ammonia gas sensors using nebulizer spray pyrolysis technique

Sodium doped zinc oxide (Na:ZnO) thin films were deposited on glass substrates at substrate temperatures 300,400 and 500 degrees C by a novel nebulizer spray method. X-ray diffraction shows that all the films are polycrystalline in nature having hexagonal structure with high preferential orientation along (0 0 2) plane. High resolution SEM studies reveal the formation of Na-doped ZnO films having uniformly distributed nano-rods over the entire surface of the substrates at 400 degrees C. The complex impedance of the ZnO nano-rods shows two distinguished semicircles and the diameter of the arcs got decreased in diameter as the temperature increases from 170 to 270 degrees C and thereafter slightly increased. (c) 2013 Elsevier B.V. All rights reserved.

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.

Carbon transition efficiency and process cost in high-rate, large-area deposition of diamond films by DC arc plasma jet

A new DC plasma torch in which are jet states and deposition parameters can be regulated over a wide range has been built. It showed advantages in producing stable plasma conditions at a small gas flow rate. Plasma jets with and without magnetically rotated arcs could be generated. With straight are jet deposition, diamond films could be formed at a rate of 39 mu m/h on Mo substrates of Phi 25 mm, and the conversion rate of carbon in CH4 to diamond was less than 3%. Under magnetically rotated conditions, diamond films could be deposited uniformly in a range of Phi 40 mm at 30 mu m/h, with a quite low total gas flow rate and high carbon conversion rate of over 11%. Mechanisms of rapid and uniform deposition of diamond films with low gas consumption and high carbon transition efficiency are discussed.

Travel time tomographic studies of seismic structures around subducted lithospheric slabs

The nature of the subducted lithospheric slab is investigated seismologically by tomographic inversions of ISC residual travel times. The slab, in which nearly all deep earthquakes occur, is fast in the seismic images because it is much cooler than the ambient mantle. High resolution three-dimensional P and S wave models in the NW Pacific are obtained using regional data, while inversion for the SW Pacific slabs includes teleseismic arrivals. Resolution and noise estimations show the models are generally well-resolved.

The slab anomalies in these models, as inferred from the seismicity, are generally coherent in the upper mantle and become contorted and decrease in amplitude with depth. Fast slabs are surrounded by slow regions shallower than 350 km depth. Slab fingering, including segmentation and spreading, is indicated near the bottom of the upper mantle. The fast anomalies associated with the Japan, Izu-Bonin, Mariana and Kermadec subduction zones tend to flatten to sub-horizontal at depth, while downward spreading may occur under parts of the Mariana and Kuril arcs. The Tonga slab appears to end around 550 km depth, but is underlain by a fast band at 750-1000 km depths.

The NW Pacific model combined with the Clayton-Comer mantle model predicts many observed residual sphere patterns. The predictions indicate that the near-source anomalies affect the residual spheres less than the teleseismic contributions. The teleseismic contributions may be removed either by using a mantle model, or using teleseismic station averages of residuals from only regional events. The slab-like fast bands in the corrected residual spheres are are consistent with seismicity trends under the Mariana Tzu-Bonin and Japan trenches, but are inconsistent for the Kuril events.

The comparison of the tomographic models with earthquake focal mechanisms shows that deep compression axes and fast velocity slab anomalies are in consistent alignment, even when the slab is contorted or flattened. Abnormal stress patterns are seen at major junctions of the arcs. The depth boundary between tension and compression in the central parts of these arcs appears to depend on the dip and topology of the slab.

二次光栅在波前测量中的应用

采用一种特殊的二次光栅用于激光波前测量, 它对非零级衍射光束具有不同的聚焦效应, 其光栅线为圆弧型而非直线。导出了在会聚光束情况下的两平面成像在单一像平面上的距离关系, 实验上实现了二次光栅用于会聚光束的波前测量, 测量得到会聚光束具有较大的散焦(-2.93λ)和球差(1.34λ), 与该透镜引起波前的离焦像差理论理想值(-2.695λ)基本符合。该技术可以实现波前的高空间分辨力和高精度实时测量, 大大减少光学元件数量, 降低装置成本。由于大功率激光束的不稳定性, 其波前变化非常快, 所以该方法的实时性非

Imaging the earth with ambient noise and earthquakes

In this thesis, I develop the velocity and structure models for the Los Angeles Basin and Southern Peru. The ultimate goal is to better understand the geological processes involved in the basin and subduction zone dynamics. The results are obtained from seismic interferometry using ambient noise and receiver functions using earthquake- generated waves. Some unusual signals specific to the local structures are also studied. The main findings are summarized as follows:

(1) Los Angeles Basin

The shear wave velocities range from 0.5 to 3.0 km/s in the sediments, with lateral gradients at the Newport-Inglewood, Compton-Los Alamitos, and Whittier Faults. The basin is a maximum of 8 km deep along the profile, and the Moho rises to a depth of 17 km under the basin. The basin has a stretch factor of 2.6 in the center decreasing to 1.3 at the edges, and is in approximate isostatic equilibrium. This "high-density" (~1 km spacing) "short-duration" (~1.5 month) experiment may serve as a prototype experiment that will allow basins to be covered by this type of low-cost survey.

(2) Peruvian subduction zone

Two prominent mid-crust structures are revealed in the 70 km thick crust under the Central Andes: a low-velocity zone interpreted as partially molten rocks beneath the Western Cordillera – Altiplano Plateau, and the underthrusting Brazilian Shield beneath the Eastern Cordillera. The low-velocity zone is oblique to the present trench, and possibly indicates the location of the volcanic arcs formed during the steepening of the Oligocene flat slab beneath the Altiplano Plateau.

The Nazca slab changes from normal dipping (~25 degrees) subduction in the southeast to flat subduction in the northwest of the study area. In the flat subduction regime, the slab subducts to ~100 km depth and then remains flat for ~300 km distance before it resumes a normal dipping geometry. The flat part closely follows the topography of the continental Moho above, indicating a strong suction force between the slab and the overriding plate. A high-velocity mantle wedge exists above the western half of the flat slab, which indicates the lack of melting and thus explains the cessation of the volcanism above. The velocity turns to normal values before the slab steepens again, indicating possible resumption of dehydration and ecologitization.

(3) Some unusual signals

Strong higher-mode Rayleigh waves due to the basin structure are observed in the periods less than 5 s. The particle motions provide a good test for distinguishing between the fundamental and higher mode. The precursor and coda waves relative to the interstation Rayleigh waves are observed, and modeled with a strong scatterer located in the active volcanic area in Southern Peru. In contrast with the usual receiver function analysis, multiples are extensively involved in this thesis. In the LA Basin, a good image is only from PpPs multiples, while in Peru, PpPp multiples contribute significantly to the final results.

Distribuição e abundância do coral invasor Tubastraea spp.

As espécies de corais invasores, Tubastraea tagusensis e T. coccinea foram acidentalmente introduzidos no Brasil através de plataformas de petróleo. O rápido crescimento e estágio reprodutivo, competição contra espécies nativas, defesas químicas contra predadores e competidores naturais e uso amplo em diferentes substratos utilizados contribuem para o sucesso e expansão de Tubastraea spp. na costa brasileira. O presente estudo teve dois objetivos principais: 1) investigar uma metodologia que resulte em uma maior eficiência e custo-benefício nos processsos de monitoramento dos corais invasores Tubastraea spp. no litoral brasileiro; 2) mapear a distribuição geográfica, caracterizar as populações e estudar o efeito da inserção dos corais na comunidade bêntica de costões rochosos do litoral norte do estado de São Paulo (LNSP). O primeiro avaliou quatro metodologias, comparando o método do censo visual, e outras três metodologias que utilizam fotografia e filmagem. O método do censo visual mostrou ser mais eficiente na obtenção dos resultados quando comparado com os outros métodos, principalmente para identificar pequenos organismos. Contudo, seu tempo em campo e seus custos foram maiores. O segundo utilizou o método visual para estudar o efeito da inserção dos corais invasores na comunidade local do LNSP. Ainda, foi realizado um monitoramento espacial semi-quantitativo em larga escala para caracterizar a distribuição espacial dos corais invasores; transectos com quadrados amostrais foram usados para estimar a densidade de Tubastraea ao longo da profundidade, e transectos e arcos graduados empregados para estimar a ocorrência de colônias em diferentes inclinações do substrato, no LNSP. Os corais invasores estão aumentado sua distribuição, causando diversos impactos nas comunidades e nos organismos nativos. T. tagusensis é comumente encontrado dominando diversos costões rochosos, com uma densidade maior em ambientes mais profundos e com maior ocorência em substratos de inclinções verticais e negativas no LNSP. A erradicação e/ou controle do coral invasor é recomendado no litoral brasileiro, principalmente onde as populações estão isoladas ou ainda são pequenas.