Hardness results for computing optimal locally Gabriel graphs

Delaunay and Gabriel graphs are widely studied geo-metric proximity structures. Motivated by applications in wireless routing, relaxed versions of these graphs known as Locally Delaunay Graphs (LDGs) and Lo-cally Gabriel Graphs (LGGs) have been proposed. We propose another generalization of LGGs called Gener-alized Locally Gabriel Graphs (GLGGs) in the context when certain edges are forbidden in the graph. Unlike a Gabriel Graph, there is no unique LGG or GLGG for a given point set because no edge is necessarily in-cluded or excluded. This property allows us to choose an LGG/GLGG that optimizes a parameter of interest in the graph. We show that computing an edge max-imum GLGG for a given problem instance is NP-hard and also APX-hard. We also show that computing an LGG on a given point set with dilation ≤k is NP-hard. Finally, we give an algorithm to verify whether a given geometric graph G= (V, E) is a valid LGG.

Detecting symmetry in scalar fields using augmented extremum graphs

Visualizing symmetric patterns in the data often helps the domain scientists make important observations and gain insights about the underlying experiment. Detecting symmetry in scalar fields is a nascent area of research and existing methods that detect symmetry are either not robust in the presence of noise or computationally costly. We propose a data structure called the augmented extremum graph and use it to design a novel symmetry detection method based on robust estimation of distances. The augmented extremum graph captures both topological and geometric information of the scalar field and enables robust and computationally efficient detection of symmetry. We apply the proposed method to detect symmetries in cryo-electron microscopy datasets and the experiments demonstrate that the algorithm is capable of detecting symmetry even in the presence of significant noise. We describe novel applications that use the detected symmetry to enhance visualization of scalar field data and facilitate their exploration.

Monotonic and low cycle fatigue behavior of an O+B2 alloy at high temperatures

Low cycle fatigue behavior of an O+B2 alloy was evaluated at 650 degrees C in ambient atmosphere under fully reversed total axial strain controlled mode. Three different microstructures, namely equiaxed O plus aged B2 (fine O plates in B2 matrix), lenticular O laths plus aged B2 and a pancake composite microstructure comprising equiaxed alpha 2, lenticular O and aged B2, were selected to study the effect of microstructure on low cycle fatigue behavior in this class of alloys. Distinct well-defined trends were observed in the cyclic stress-strain response curves depending on the microstructure. The cyclic stress response was examined in terms of softening or hardening and correlated with microstructural features and dislocation behavior. Fatigue life was analyzed in terms of standard Coffin-Manson and Basquin plots and for all microstructures a prevailing elastic strain regime was identified, with a single slope for microstructures equiaxed and composite and a double slope for lenticular O laths. (c) 2014 Elsevier B.V. All rights reserved.

A modeling study of the processes of surface salinity seasonal cycle in the Bay of Bengal

In response to the Indian Monsoon freshwater forcing, the Bay of Bengal exhibits a very strong seasonal cycle in sea surface salinity (SSS), especially near the mouths of the Ganges-Brahmaputra and along the east coast of India. In this paper, we use an eddy-permitting (similar to 25 km resolution) regional ocean general circulation model simulation to quantify the processes responsible for this SSS seasonal cycle. Despite the absence of relaxation toward observations, the model reproduces the main features of the observed SSS seasonal cycle, with freshest water in the northeastern Bay, particularly during and after the monsoon. The model also displays an intense and shallow freshening signal in a narrow (similar to 100 km wide) strip that hugs the east coast of India, from September to January, in good agreement with high-resolution measurements along two ships of opportunity lines. The mixed layer salt budget confirms that the strong freshening in the northern Bay during the monsoon results from the Ganges-Brahmaputra river discharge and from precipitation over the ocean. From September onward, the East India Coastal Current transports this freshwater southward along the east coast of India, reaching the southern tip of India in November. The surface freshening results in an enhanced vertical salinity gradient that increases salinity of the surface layer by vertical processes. Our results reveal that the erosion of the freshwater tongue along the east coast of India is not driven by northward horizontal advection, but by vertical processes that eventually overcome the freshening by southward advection and restore SSS to its premonsoon values. The salinity-stratified barrier layer hence only acts as a ``barrier'' for vertical heat fluxes, but is associated with intense vertical salt fluxes in the Bay of Bengal.

POLAR NETWORK INDEX AS A MAGNETIC PROXY FOR THE SOLAR CYCLE STUDIES

The Sun has a polar magnetic field which oscillates with the 11 yr sunspot cycle. This polar magnetic field is an important component of the dynamo process which operates in the solar convection zone and produces the sunspot cycle. We have direct systematic measurements of the Sun's polar magnetic field only from about the mid-1970s. There are, however, indirect proxies which give us information about this field at earlier times. The Ca-K spectroheliograms taken at the Kodaikanal Solar Observatory during 1904-2007 have now been digitized with 4k x 4k CCD and have higher resolution (similar to 0.86 arcsec) than the other available historical data sets. From these Ca-K spectroheliograms, we have developed a completely new proxy (polar network index, hereafter PNI) for the Sun's polar magnetic field. We calculate PNI from the digitized images using an automated algorithm and calibrate our measured PNI against the polar field as measured by the Wilcox Solar Observatory for the period 1976-1990. This calibration allows us to estimate the polar fields for the earlier period up to 1904. The dynamo calculations performed with this proxy as input data reproduce reasonably well the Sun's magnetic behavior for the past century.

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.

2-Connecting outerplanar graphs without blowing up the pathwidth

Given a connected outerplanar graph G of pathwidth p, we give an algorithm to add edges to G to get a supergraph of G, which is 2-vertex-connected, outerplanar and of pathwidth O(p). This settles an open problem raised by Biedl 1], in the context of computing minimum height planar straight line drawings of outerplanar graphs, with their vertices placed on a two-dimensional grid. In conjunction with the result of this paper, the constant factor approximation algorithm for this problem obtained by Biedl 1] for 2-vertex-connected outerplanar graphs will work for all outer planar graphs. (C) 2014 Elsevier B.V. All rights reserved.

Parameterized Algorithms for MAX COLORABLE INDUCED SUBGRAPH Problem on Perfect Graphs

We address the parameterized complexity ofMaxColorable Induced Subgraph on perfect graphs. The problem asks for a maximum sized q-colorable induced subgraph of an input graph G. Yannakakis and Gavril IPL 1987] showed that this problem is NP-complete even on split graphs if q is part of input, but gave a n(O(q)) algorithm on chordal graphs. We first observe that the problem is W2]-hard parameterized by q, even on split graphs. However, when parameterized by l, the number of vertices in the solution, we give two fixed-parameter tractable algorithms. The first algorithm runs in time 5.44(l) (n+#alpha(G))(O(1)) where #alpha(G) is the number of maximal independent sets of the input graph. The second algorithm runs in time q(l+o()l())n(O(1))T(alpha) where T-alpha is the time required to find a maximum independent set in any induced subgraph of G. The first algorithm is efficient when the input graph contains only polynomially many maximal independent sets; for example split graphs and co-chordal graphs. The running time of the second algorithm is FPT in l alone (whenever T-alpha is a polynomial in n), since q <= l for all non-trivial situations. Finally, we show that (under standard complexitytheoretic assumptions) the problem does not admit a polynomial kernel on split and perfect graphs in the following sense: (a) On split graphs, we do not expect a polynomial kernel if q is a part of the input. (b) On perfect graphs, we do not expect a polynomial kernel even for fixed values of q >= 2.

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

The irregularities of the sunspot cycle and their theoretical modelling

The 11-year sunspot cycle has many irregularities, the most prominent amongst them being the grand minima when sunspots may not be seen for several cycles. After summarizing the relevant observational data about the irregularities, we introduce the flux transport dynamo model, the currently most successful theoretical model for explaining the 11-year sunspot cycle. Then we analyze the respective roles of nonlinearities and random fluctuations in creating the irregularities. We also discuss how it has recently been realized that the fluctuations in meridional circulation also can be a source of irregularities. We end by pointing out that fluctuations in the poloidal field generation and fluctuations in meridional circulation together can explain the occurrences of grand minima.

Rainbow matchings in strongly edge-colored graphs

A rainbow matching of an edge-colored graph G is a matching in which no two edges have the same color. There have been several studies regarding the maximum size of a rainbow matching in a properly edge-colored graph G in terms of its minimum degree 3(G). Wang (2011) asked whether there exists a function f such that a properly edge-colored graph G with at least f (delta(G)) vertices is guaranteed to contain a rainbow matching of size delta(G). This was answered in the affirmative later: the best currently known function Lo and Tan (2014) is f(k) = 4k - 4, for k >= 4 and f (k) = 4k - 3, for k <= 3. Afterwards, the research was focused on finding lower bounds for the size of maximum rainbow matchings in properly edge-colored graphs with fewer than 4 delta(G) - 4 vertices. Strong edge-coloring of a graph G is a restriction of proper edge-coloring where every color class is required to be an induced matching, instead of just being a matching. In this paper, we give lower bounds for the size of a maximum rainbow matching in a strongly edge-colored graph Gin terms of delta(G). We show that for a strongly edge-colored graph G, if |V(G)| >= 2 |3 delta(G)/4|, then G has a rainbow matching of size |3 delta(G)/4|, and if |V(G)| < 2 |3 delta(G)/4|, then G has a rainbow matching of size |V(G)|/2] In addition, we prove that if G is a strongly edge-colored graph that is triangle-free, then it contains a rainbow matching of size at least delta(G). (C) 2015 Elsevier B.V. All rights reserved.

SEPARATION DIMENSION OF BOUNDED DEGREE GRAPHS

The separation dimension of a graph G is the smallest natural number k for which the vertices of G can be embedded in R-k such that any pair of disjoint edges in G can be separated by a hyperplane normal to one of the axes. Equivalently, it is the smallest possible cardinality of a family F of total orders of the vertices of G such that for any two disjoint edges of G, there exists at least one total order in F in which all the vertices in one edge precede those in the other. In general, the maximum separation dimension of a graph on n vertices is Theta(log n). In this article, we focus on bounded degree graphs and show that the separation dimension of a graph with maximum degree d is at most 2(9) (log*d)d. We also demonstrate that the above bound is nearly tight by showing that, for every d, almost all d-regular graphs have separation dimension at least d/2]

Boxicity and cubicity of product graphs

The boxicity (cubicity) of a graph G is the minimum natural number k such that G can be represented as an intersection graph of axis-parallel rectangular boxes (axis-parallel unit cubes) in R-k. In this article, we give estimates on the boxicity and the cubicity of Cartesian, strong and direct products of graphs in terms of invariants of the component graphs. In particular, we study the growth, as a function of d, of the boxicity and the cubicity of the dth power of a graph with respect to the three products. Among others, we show a surprising result that the boxicity and the cubicity of the dth Cartesian power of any given finite graph is, respectively, in O(log d/ log log d) and circle dot(d/ log d). On the other hand, we show that there cannot exist any sublinear bound on the growth of the boxicity of powers of a general graph with respect to strong and direct products. (C) 2015 Elsevier Ltd. All rights reserved.

Heterochromatic paths in edge colored graphs without small cycles and heterochromatic-triangle-free graphs

Conditions for the existence of heterochromatic Hamiltonian paths and cycles in edge colored graphs are well investigated in literature. A related problem in this domain is to obtain good lower bounds for the length of a maximum heterochromatic path in an edge colored graph G. This problem is also well explored by now and the lower bounds are often specified as functions of the minimum color degree of G - the minimum number of distinct colors occurring at edges incident to any vertex of G - denoted by v(G). Initially, it was conjectured that the lower bound for the length of a maximum heterochromatic path for an edge colored graph G would be 2v(G)/3]. Chen and Li (2005) showed that the length of a maximum heterochromatic path in an edge colored graph G is at least v(G) - 1, if 1 <= v(G) <= 7, and at least 3v(G)/5] + 1 if v(G) >= 8. They conjectured that the tight lower bound would be v(G) - 1 and demonstrated some examples which achieve this bound. An unpublished manuscript from the same authors (Chen, Li) reported to show that if v(G) >= 8, then G contains a heterochromatic path of length at least 120 + 1. In this paper, we give lower bounds for the length of a maximum heterochromatic path in edge colored graphs without small cycles. We show that if G has no four cycles, then it contains a heterochromatic path of length at least v(G) - o(v(G)) and if the girth of G is at least 4 log(2)(v(G)) + 2, then it contains a heterochromatic path of length at least v(G) - 2, which is only one less than the bound conjectured by Chen and Li (2005). Other special cases considered include lower bounds for the length of a maximum heterochromatic path in edge colored bipartite graphs and triangle-free graphs: for triangle-free graphs we obtain a lower bound of 5v(G)/6] and for bipartite graphs we obtain a lower bound of 6v(G)-3/7]. In this paper, it is also shown that if the coloring is such that G has no heterochromatic triangles, then G contains a heterochromatic path of length at least 13v(G)/17)]. This improves the previously known 3v(G)/4] bound obtained by Chen and Li (2011). We also give a relatively shorter and simpler proof showing that any edge colored graph G contains a heterochromatic path of length at least (C) 2015 Elsevier Ltd. All rights reserved.

DNA intercalative 4-butylaminopyrimido4',5':4,5]thieno(2,3-b)quinoline induces cell cycle arrest and apoptosis in leukemia cells

DNA intercalators are one of the interesting groups in cancer chemotherapy. The development of novel anticancer small molecule has gained remarkable interest over the last decade. In this study, we synthesized and investigated the ability of a tetracyclic-condensed quinoline compound, 4-butylaminopyrimido4',5':4,5]thieno(2,3-b)quinoline (BPTQ), to interact with double-stranded DNA and inhibit cancer cell proliferation. Circular dichroism, topological studies, molecular docking, absorbance, and fluorescence spectral titrations were employed to study the interaction of BPTQ with DNA. Cytotoxicity was studied by performing 3-(4,5-dimethylthiazol-2-yl)-2,5-diphenyltetrazolium bromide (MTT) and lactate dehydrogenase (LDH) assay. Further, cell cycle analysis by flow cytometry, annexin V staining, mitochondrial membrane potential assay, DNA fragmentation, and western blot analysis were used to elucidate the mechanism of action of BPTQ at the cellular level. Spectral, topological, and docking studies confirmed that BPTQ is a typical intercalator of DNA. BPTQ induces dose-dependent inhibitory effect on the proliferation of cancer cells by arresting cells at S and G2/M phase. Further, BPTQ activates the mitochondria-mediated apoptosis pathway, as explicated by a decrease in mitochondrial membrane potential, increase in the Bax:Bcl-2 ratio, and activation of caspases. These results confirmed that BPTQ is a DNA intercalative anticancer molecule, which could aid in the development of future cancer therapeutic agents.