Rainbow connection number and connected dominating sets

The rainbow connection number of a connected graph is the minimum number of colors needed to color its edges, so that every pair of its vertices is connected by at least one path in which no two edges are colored the same. In this article we show that for every connected graph on n vertices with minimum degree delta, the rainbow connection number is upper bounded by 3n/(delta + 1) + 3. This solves an open problem from Schiermeyer (Combinatorial Algorithms, Springer, Berlin/Hiedelberg, 2009, pp. 432437), improving the previously best known bound of 20n/delta (J Graph Theory 63 (2010), 185191). This bound is tight up to additive factors by a construction mentioned in Caro et al. (Electr J Combin 15(R57) (2008), 1). As an intermediate step we obtain an upper bound of 3n/(delta + 1) - 2 on the size of a connected two-step dominating set in a connected graph of order n and minimum degree d. This bound is tight up to an additive constant of 2. This result may be of independent interest. We also show that for every connected graph G with minimum degree at least 2, the rainbow connection number, rc(G), is upper bounded by Gc(G) + 2, where Gc(G) is the connected domination number of G. Bounds of the form diameter(G)?rc(G)?diameter(G) + c, 1?c?4, for many special graph classes follow as easy corollaries from this result. This includes interval graphs, asteroidal triple-free graphs, circular arc graphs, threshold graphs, and chain graphs all with minimum degree delta at least 2 and connected. We also show that every bridge-less chordal graph G has rc(G)?3.radius(G). In most of these cases, we also demonstrate the tightness of the bounds.

Maximum weight independent sets in hole- and dart-free graphs

The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. The complexity of the MWIS problem for hole-free graphs is unknown. In this paper, we first prove that the MWIS problem for (hole, dart, gem)-free graphs can be solved in O(n(3))-time. By using this result, we prove that the MWIS problem for (hole, dart)-free graphs can be solved in O(n(4))-time. Though the MWIS problem for (hole, dart, gem)-free graphs is used as a subroutine, we also give the best known time bound for the solvability of the MWIS problem in (hole, dart, gem)-free graphs. (C) 2012 Elsevier B.V. All rights reserved.

A numerical approach to determine the sufficiency of given boundary data sets for uniquely estimating interior elastic properties

We consider an inverse elasticity problem in which forces and displacements are known on the boundary and the material property distribution inside the body is to be found. In other words, we need to estimate the distribution of constitutive properties using the finite boundary data sets. Uniqueness of the solution to this problem is proved in the literature only under certain assumptions for a given complete Dirichlet-to-Neumann map. Another complication in the numerical solution of this problem is that the number of boundary data sets needed to establish uniqueness is not known even under the restricted cases where uniqueness is proved theoretically. In this paper, we present a numerical technique that can assess the sufficiency of given boundary data sets by computing the rank of a sensitivity matrix that arises in the Gauss-Newton method used to solve the problem. Numerical experiments are presented to illustrate the method.

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.

Fully complex-valued ELM classifiers for human action recognition

In this paper, we present a fast learning neural network classifier for human action recognition. The proposed classifier is a fully complex-valued neural network with a single hidden layer. The neurons in the hidden layer employ the fully complex-valued hyperbolic secant as an activation function. The parameters of the hidden layer are chosen randomly and the output weights are estimated analytically as a minimum norm least square solution to a set of linear equations. The fast leaning fully complex-valued neural classifier is used for recognizing human actions accurately. Optical flow-based features extracted from the video sequences are utilized to recognize 10 different human actions. The feature vectors are computationally simple first order statistics of the optical flow vectors, obtained from coarse to fine rectangular patches centered around the object. The results indicate the superior performance of the complex-valued neural classifier for action recognition. The superior performance of the complex neural network for action recognition stems from the fact that motion, by nature, consists of two components, one along each of the axes.

Benchmarking recognition results on camera captured word image data sets

We have benchmarked the maximum obtainable recognition accuracy on five publicly available standard word image data sets using semi-automated segmentation and a commercial OCR. These images have been cropped from camera captured scene images, born digital images (BDI) and street view images. Using the Matlab based tool developed by us, we have annotated at the pixel level more than 3600 word images from the five data sets. The word images binarized by the tool, as well as by our own midline analysis and propagation of segmentation (MAPS) algorithm are recognized using the trial version of Nuance Omnipage OCR and these two results are compared with the best reported in the literature. The benchmark word recognition rates obtained on ICDAR 2003, Sign evaluation, Street view, Born-digital and ICDAR 2011 data sets are 83.9%, 89.3%, 79.6%, 88.5% and 86.7%, respectively. The results obtained from MAPS binarized word images without the use of any lexicon are 64.5% and 71.7% for ICDAR 2003 and 2011 respectively, and these values are higher than the best reported values in the literature of 61.1% and 41.2%, respectively. MAPS results of 82.8% for BDI 2011 dataset matches the performance of the state of the art method based on power law transform.

Covariance profiles: a signature representation for object sets

We consider the problem of extracting a signature representation of similar entities employing covariance descriptors. Covariance descriptors can efficiently represent objects and are robust to scale and pose changes. We posit that covariance descriptors corresponding to similar objects share a common geometrical structure which can be extracted through joint diagonalization. We term this diagonalizing matrix as the Covariance Profile (CP). CP can be used to measure the distance of a novel object to an object set through the diagonality measure. We demonstrate how CP can be employed on images as well as for videos, for applications such as face recognition and object-track clustering.

Subject independent human action recognition using spatio-depth information and meta-cognitive RBF network

In this paper, we present a machine learning approach for subject independent human action recognition using depth camera, emphasizing the importance of depth in recognition of actions. The proposed approach uses the flow information of all 3 dimensions to classify an action. In our approach, we have obtained the 2-D optical flow and used it along with the depth image to obtain the depth flow (Z motion vectors). The obtained flow captures the dynamics of the actions in space time. Feature vectors are obtained by averaging the 3-D motion over a grid laid over the silhouette in a hierarchical fashion. These hierarchical fine to coarse windows capture the motion dynamics of the object at various scales. The extracted features are used to train a Meta-cognitive Radial Basis Function Network (McRBFN) that uses a Projection Based Learning (PBL) algorithm, referred to as PBL-McRBFN, henceforth. PBL-McRBFN begins with zero hidden neurons and builds the network based on the best human learning strategy, namely, self-regulated learning in a meta-cognitive environment. When a sample is used for learning, PBLMcRBFN uses the sample overlapping conditions, and a projection based learning algorithm to estimate the parameters of the network. The performance of PBL-McRBFN is compared to that of a Support Vector Machine (SVM) and Extreme Learning Machine (ELM) classifiers with representation of every person and action in the training and testing datasets. Performance study shows that PBL-McRBFN outperforms these classifiers in recognizing actions in 3-D. Further, a subject-independent study is conducted by leave-one-subject-out strategy and its generalization performance is tested. It is observed from the subject-independent study that McRBFN is capable of generalizing actions accurately. The performance of the proposed approach is benchmarked with Video Analytics Lab (VAL) dataset and Berkeley Multimodal Human Action Database (MHAD). (C) 2013 Elsevier Ltd. All rights reserved.

Antithyroid drugs and their analogues: synthesis, structure, and mechanism of action

Thyroid hormones are essential for the development and differentiation of all cells of the human body. They regulate protein, fat, and carbohydrate metabolism. In this Account, we discuss the synthesis, structure, and mechanism of action of thyroid hormones and their analogues. The prohormone thyroxine (14) is synthesized on thyroglobulin by thyroid peroxidase (TPO), a heme enzyme that uses iodide and hydrogen peroxide to perform iodination and phenolic coupling reactions. The monodeiodination of T4 to 3,3',5-triiodothyronine (13) by selenium-containing deiodinases (ID-1, ID-2) is a key step in the activation of thyroid hormones. The type 3 deiodinase (ID-3) catalyzes the deactivation of thyroid hormone in a process that removes iodine selectively from the tyrosyl ring of T4 to produce 3,3',5'-triiodothyronine (rT3). Several physiological and pathological stimuli influence thyroid hormone synthesis. The overproduction of thyroid hormones leads to hyperthyroidism, which is treated by antithyroid drugs that either inhibit the thyroid hormone biosynthesis and/or decrease the conversion of T4 to T3. Antithyroid drugs are thiourea-based compounds, which indude propylthiouracil (PTU), methimazole (MM I), and carbimazole (CBZ). The thyroid gland actively concentrates these heterocyclic compounds against a concentration gradient Recently, the selenium analogues of PTU, MMI, and CBZ attracted significant attention because the selenium moiety in these compounds has a higher nucleophilicity than that of the sulfur moiety. Researchers have developed new methods for the synthesis of the selenium compounds. Several experimental and theoretical investigations revealed that the selone (C=Se) in the selenium analogues is more polarized than the thione (C=S) in the sulfur compounds, and the selones exist predominantly in their zwitterionic forms. Although the thionamide-based antithyroid drugs have been used for almost 70 years, the mechanism of their action is not completely understood. Most investigations have revealed that MMI and PTU irreversibly inhibit TPO. PTU, MTU, and their selenium analogues also inhibit ID-1, most likely by reacting with the selenenyl iodide intermediate. The good ID-1 inhibitory activity of Pill and its analogues can be ascribed to the presence of the -N(H)-C(=O)- functionality that can form hydrogen bonds with nearby amino add residues in the selenenyl sulfide state. In addition to the TPO and ID-1 inhibition, the selenium analogues are very good antioxidants. In the presence of cellular reducing agents such as GSH, these compounds catalytically reduce hydrogen peroxide. They can also efficiently scavenge peroxynitrite, a potent biological oxidant and nitrating agent.

Differential Action of Glycoprotein Hormones: Significance in Cancer Progression

Growth of multicellular organisms depends on maintenance of proper balance between proliferation and differentiation. Any disturbance in this balance in animal cells can lead to cancer. Experimental evidence is provided to conclude with special reference to the action of follicle-stimulating hormone (FSH) on Sertoli cells, and luteinizing hormone (LH) on Leydig cells that these hormones exert a differential action on their target cells, i.e., stimulate proliferation when the cells are in an undifferentiated state which is the situation with cancer cells and promote only functional parameters when the cell are fully differentiated. Hormones and growth factors play a key role in cell proliferation, differentiation, and apoptosis. There is a growing body of evidence that various tumors express some hormones at high levels as well as their cognate receptors indicating the possibility of a role in progression of cancer. Hormones such as LH, FSH, and thyroid-stimulating hormone have been reported to stimulate cell proliferation and act as tumor promoter in a variety of hormone-dependent cancers including gonads, lung, thyroid, uterus, breast, prostate, etc. This review summarizes evidence to conclude that these hormones are produced by some cancer tissues to promote their own growth. Also an attempt is made to explain the significance of the differential action of hormones in progression of cancer with special reference to prostate cancer.

RAPID HUMAN ACTION RECOGNITION IN H.264/AVC COMPRESSED DOMAIN FOR VIDEO SURVEILLANCE

This paper discusses a novel high-speed approach for human action recognition in H. 264/AVC compressed domain. The proposed algorithm utilizes cues from quantization parameters and motion vectors extracted from the compressed video sequence for feature extraction and further classification using Support Vector Machines (SVM). The ultimate goal of our work is to portray a much faster algorithm than pixel domain counterparts, with comparable accuracy, utilizing only the sparse information from compressed video. Partial decoding rules out the complexity of full decoding, and minimizes computational load and memory usage, which can effect in reduced hardware utilization and fast recognition results. The proposed approach can handle illumination changes, scale, and appearance variations, and is robust in outdoor as well as indoor testing scenarios. We have tested our method on two benchmark action datasets and achieved more than 85% accuracy. The proposed algorithm classifies actions with speed (>2000 fps) approximately 100 times more than existing state-of-the-art pixel-domain algorithms.

Consequences of Converting Graded to Action Potentials upon Neural Information Coding and Energy Efficiency

Information is encoded in neural circuits using both graded and action potentials, converting between them within single neurons and successive processing layers. This conversion is accompanied by information loss and a drop in energy efficiency. We investigate the biophysical causes of this loss of information and efficiency by comparing spiking neuron models, containing stochastic voltage-gated Na+ and K+ channels, with generator potential and graded potential models lacking voltage-gated Na+ channels. We identify three causes of information loss in the generator potential that are the by-product of action potential generation: (1) the voltage-gated Na+ channels necessary for action potential generation increase intrinsic noise and (2) introduce non-linearities, and (3) the finite duration of the action potential creates a `footprint' in the generator potential that obscures incoming signals. These three processes reduce information rates by similar to 50% in generator potentials, to similar to 3 times that of spike trains. Both generator potentials and graded potentials consume almost an order of magnitude less energy per second than spike trains. Because of the lower information rates of generator potentials they are substantially less energy efficient than graded potentials. However, both are an order of magnitude more efficient than spike trains due to the higher energy costs and low information content of spikes, emphasizing that there is a two-fold cost of converting analogue to digital; information loss and cost inflation.

Design and Synthesis of New Benzimidazole-Carbazole Conjugates for the Stabilization of Human Telomeric DNA, Telomerase Inhibition, and Their Selective Action on Cancer Cells

Cell-permeable small molecules that enhance the stability of the G-quadruplex (G4) DNA structures are currently among the most intensively pursued ligands for inhibition of the telomerase activity. Herein we report the design and syntheses of four novel benzimidazole carbazole conjugates and demonstrate their high binding affinity to G4 DNA. Si nuclease assay confirmed the ligand mediated G-quadruplex DNA protection. Additional evidence from Telomeric Repeat Amplification Protocol (TRAP-LIG) assay demonstrated efficient telomerase inhibition activity by the ligands. Two of the ligands showed IC50 values in the sub-micromolar range in the TRAP-LIG assay, which are the best among the benzimidazole derivatives reported so far. The ligands also exhibited cancer cell selective nuclear internalization, nuclear condensation, fragmentation, and eventually antiproliferative activity in long-term cell viability assays. Annexin V-FITC/PI staining assays confirm that the cell death induced by the ligands follows an apoptotic pathway. An insight into the mode of ligand binding was obtained from the molecular dynamics simulations.

2-(4-Chlorobenzyl)-6-arylimidazo2,1-b]1,3,4]thiadiazoles: Synthesis, cytotoxic activity and mechanism of action

The cytotoxic activity of a new series of 2-(4'-chlorobenzyl)-5,6-disubstituted imidazo2,1-b]1,3,4]wthiadiazoles against different human and murine cancer cell lines is reported. Among the tested compounds, two derivatives namely 2-(4-chlorobenzyl)-6-(2-oxo-2H-chromen-3-yl)imidazo2,1-1)]1,3,4]th iadiazole-5-carbaldehyde 4i and 2-(4-chlorobenzyl)-6-(2-oxo-2H-chromen-3-ypimidazo2,1-1)]1,3,4]thi adiazol-5-yl thiocyanate 5i emerged as the most potent against all the cell lines. To investigate the mechanism of action, we selected compounds 4i for cell cycle study, analysis of mitochondrial membrane potential and Annexin V-FITC flow cytometric analysis and DNA fragmentation assay. Results showed that 4i induced cytotoxicity by inducing apoptosis without arresting the cell cycle. (C) 2014 Elsevier Masson SAS. All rights reserved.