A canonical form for nonderogatory matrices under unitary similarity

A square matrix is nonderogatory if its Jordan blocks have distinct eigenvalues. We give canonical forms for (1) nonderogatory complex matrices up to unitary similarity, and (2) pairs of complex matrices up to similarity, in which one matrix has distinct eigenvalues. The types of these canonical forms are given by undirected and, respectively, directed graphs with no undirected cycles. (C) 2011 Elsevier Inc. All rights reserved.

PARALLEL ALGORITHMS FOR MAXIMAL CLIQUES IN CIRCLE GRAPHS AND UNRESTRICTED DEPTH SEARCH

We present parallel algorithms on the BSP/CGM model, with p processors, to count and generate all the maximal cliques of a circle graph with n vertices and m edges. To count the number of all the maximal cliques, without actually generating them, our algorithm requires O(log p) communication rounds with O(nm/p) local computation time. We also present an algorithm to generate the first maximal clique in O(log p) communication rounds with O(nm/p) local computation, and to generate each one of the subsequent maximal cliques this algorithm requires O(log p) communication rounds with O(m/p) local computation. The maximal cliques generation algorithm is based on generating all maximal paths in a directed acyclic graph, and we present an algorithm for this problem that uses O(log p) communication rounds with O(m/p) local computation for each maximal path. We also show that the presented algorithms can be extended to the CREW PRAM model.

Differential Antitumor Effects of IgG and IgM Monoclonal Antibodies and Their Synthetic Complementarity-Determining Regions Directed to New Targets of B16F10-Nex2 Melanoma Cells

Malignant melanoma has increased incidence worldwide and causes most skin cancer-related deaths. A few cell surface antigens that can be targets of antitumor immunotherapy have been characterized in melanoma. This is an expanding field because of the ineffectiveness of conventional cancer therapy for the metastatic form of melanoma. In the present work, antimelanoma monoclonal antibodies (mAbs) were raised against B16F10 cells (subclone Nex4, grown in murine serum), with novel specificities and antitumor effects in vitro and in vivo. MAb A4 (IgG2ak) recognizes a surface antigen on B16F10-Nex2 cells identified as protocadherin beta(13). It is cytotoxic in vitro and in vivo to B16F10-Nex2 cells as well as in vitro to human melanoma cell lines. MAb A4M (IgM) strongly reacted with nuclei of permeabilized murine tumor cells, recognizing histone 1. Although it is not cytotoxic in vitro, similarly with mAb A4, mAb A4M significantly reduced the number of lung nodules in mice challenged intravenously with B16F10-Nex2 cells. The V(H) CDR3 peptide from mAb A4 and V(L) CDR1 and CDR2 from mAb A4M showed significant cytotoxic activities in vitro, leading tumor cells to apoptosis. A cyclic peptide representing A4 CDR H3 competed with mAb A4 for binding to melanoma cells. MAb A4M CDRs L1 and L2 in addition to the antitumor effect also inhibited angiogenesis of human umbilical vein endothelial cells in vitro. As shown in the present work, mAbs A4 and A4M and selected CDR peptides are strong candidates to be developed as drugs for antitumor therapy for invasive melanoma.

Site-directed mutagenesis and structural modeling of Coq10p indicate the presence of a tunnel for coenzyme Q6 binding

Coq10p is a protein required for coenzyme Q function, but its specific role is still unknown. It is a member of the START domain superfamily that contains a hydrophobic tunnel implicated in the binding of lipophilic molecules. We used site-directed mutagenesis, statistical coupling analysis and molecular modeling to probe structural determinants in the Coq10p putative tunnel. Four point mutations were generated (coq10-K50E, coq10-L96S, coq10-E105K and coq10-K162D) and their biochemical properties analysed, as well as structural consequences. Our results show that all mutations impaired Coq10p function and together with molecular modeling indicate an important role for the Coq10p putative tunnel. (C) 2010 Federation of European Biochemical Societies. Published by Elsevier B.V. All rights reserved.

NeXSPheRIO results on elliptic flow and directed flow for Au plus Au and Cu plus Cu collisions at RHIC

Hydrodynamics has been rather successful at describing results obtained in relativistic nuclear collisions at RHIC. Here we show results obtained with NeXSPheRIO on Au+Au collisions and the less studied Cu+Cu collisions. We study elliptic flow and its connection with eccentricity suggested by PHOBOS, as well as present elliptic flow fluctuations. We also show results for directed flow and compare with PHOBOS and STAR data.

Texture analysis using graphs generated by deterministic partially self-avoiding walks

Texture is one of the most important visual attributes for image analysis. It has been widely used in image analysis and pattern recognition. A partially self-avoiding deterministic walk has recently been proposed as an approach for texture analysis with promising results. This approach uses walkers (called tourists) to exploit the gray scale image contexts in several levels. Here, we present an approach to generate graphs out of the trajectories produced by the tourist walks. The generated graphs embody important characteristics related to tourist transitivity in the image. Computed from these graphs, the statistical position (degree mean) and dispersion (entropy of two vertices with the same degree) measures are used as texture descriptors. A comparison with traditional texture analysis methods is performed to illustrate the high performance of this novel approach. (C) 2011 Elsevier Ltd. All rights reserved.

Engineering of 3D self-directed quantum dot ordering in multilayer InGaAs/GaAs nanostructures by means of flux gas composition

Lateral ordering of InGaAs quantum dots on the GaAs (001) surface has been achieved in earlier reports, resembling an anisotropic pattern. In this work, we present a method of breaking the anisotropy of ordered quantum dots (QDs) by changing the growth environment. We show experimentally that using As(2) molecules instead of As(4) as a background flux is efficient in controlling the diffusion of distant Ga adatoms to make it possible to produce isotropic ordering of InGaAs QDs over GaAs (001). The control of the lateral ordering of QDs under As(2) flux has enabled us to improve their optical properties. Our results are consistent with reported experimental and theoretical data for structure and diffusion on the GaAs surface.

Directed self-assembly of quantum structures by nanomechanical stamping using probe tips

We demonstrate that nanomechanically stamped substrates can be used as templates to pattern and direct the self-assembly of epitaxial quantum structures such as quantum dots. Diamond probe tips are used to indent or stamp the surface of GaAs( 100) to create nanoscale volumes of dislocation-mediated deformation, which alter the growth surface strain. These strained sites act to bias nucleation, hence allowing for selective growth of InAs quantum dots. Patterns of quantum dots are observed to form above the underlying nanostamped template. The strain state of the patterned structures is characterized by micro-Raman spectroscopy. The potential of using nanoprobe tips as a quantum dot nanofabrication technology are discussed.

Structural matching of 2D electrophoresis gels using deformed graphs

2D electrophoresis is a well-known method for protein separation which is extremely useful in the field of proteomics. Each spot in the image represents a protein accumulation and the goal is to perform a differential analysis between pairs of images to study changes in protein content. It is thus necessary to register two images by finding spot correspondences. Although it may seem a simple task, generally, the manual processing of this kind of images is very cumbersome, especially when strong variations between corresponding sets of spots are expected (e.g. strong non-linear deformations and outliers). In order to solve this problem, this paper proposes a new quadratic assignment formulation together with a correspondence estimation algorithm based on graph matching which takes into account the structural information between the detected spots. Each image is represented by a graph and the task is to find a maximum common subgraph. Successful experimental results using real data are presented, including an extensive comparative performance evaluation with ground-truth data. (C) 2010 Elsevier B.V. All rights reserved.

Performance evaluation of routing protocols for MANETs with known connectivity patterns using evolving graphs

The assessment of routing protocols for mobile wireless networks is a difficult task, because of the networks` dynamic behavior and the absence of benchmarks. However, some of these networks, such as intermittent wireless sensors networks, periodic or cyclic networks, and some delay tolerant networks (DTNs), have more predictable dynamics, as the temporal variations in the network topology can be considered as deterministic, which may make them easier to study. Recently, a graph theoretic model-the evolving graphs-was proposed to help capture the dynamic behavior of such networks, in view of the construction of least cost routing and other algorithms. The algorithms and insights obtained through this model are theoretically very efficient and intriguing. However, there is no study about the use of such theoretical results into practical situations. Therefore, the objective of our work is to analyze the applicability of the evolving graph theory in the construction of efficient routing protocols in realistic scenarios. In this paper, we use the NS2 network simulator to first implement an evolving graph based routing protocol, and then to use it as a benchmark when comparing the four major ad hoc routing protocols (AODV, DSR, OLSR and DSDV). Interestingly, our experiments show that evolving graphs have the potential to be an effective and powerful tool in the development and analysis of algorithms for dynamic networks, with predictable dynamics at least. In order to make this model widely applicable, however, some practical issues still have to be addressed and incorporated into the model, like adaptive algorithms. We also discuss such issues in this paper, as a result of our experience.

Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width

Let M = (V, E, A) be a mixed graph with vertex set V, edge set E and arc set A. A cycle cover of M is a family C = {C(1), ... , C(k)} of cycles of M such that each edge/arc of M belongs to at least one cycle in C. The weight of C is Sigma(k)(i=1) vertical bar C(i)vertical bar. The minimum cycle cover problem is the following: given a strongly connected mixed graph M without bridges, find a cycle cover of M with weight as small as possible. The Chinese postman problem is: given a strongly connected mixed graph M, find a minimum length closed walk using all edges and arcs of M. These problems are NP-hard. We show that they can be solved in polynomial time if M has bounded tree-width. (C) 2008 Elsevier B.V. All rights reserved.

Algorithms for Maximum Independent Set in Convex Bipartite Graphs

A bipartite graph G = (V, W, E) is convex if there exists an ordering of the vertices of W such that, for each v. V, the neighbors of v are consecutive in W. We describe both a sequential and a BSP/CGM algorithm to find a maximum independent set in a convex bipartite graph. The sequential algorithm improves over the running time of the previously known algorithm and the BSP/CGM algorithm is a parallel version of the sequential one. The complexity of the algorithms does not depend on |W|.

Packing triangles in low degree graphs and indifference graphs

We consider the problems of finding the maximum number of vertex-disjoint triangles (VTP) and edge-disjoint triangles (ETP) in a simple graph. Both problems are NP-hard. The algorithm with the best approximation ratio known so far for these problems has ratio 3/2 + epsilon, a result that follows from a more general algorithm for set packing obtained by Hurkens and Schrijver [On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems, SIAM J. Discrete Math. 2(1) (1989) 68-72]. We present improvements on the approximation ratio for restricted cases of VTP and ETP that are known to be APX-hard: we give an approximation algorithm for VTP on graphs with maximum degree 4 with ratio slightly less than 1.2, and for ETP on graphs with maximum degree 5 with ratio 4/3. We also present an exact linear-time algorithm for VTP on the class of indifference graphs. (C) 2007 Elsevier B.V. All rights reserved.

Sparse partition universal graphs for graphs of bounded degree

In 1983, Chvatal, Trotter and the two senior authors proved that for any Delta there exists a constant B such that, for any n, any 2-colouring of the edges of the complete graph K(N) with N >= Bn vertices yields a monochromatic copy of any graph H that has n vertices and maximum degree Delta. We prove that the complete graph may be replaced by a sparser graph G that has N vertices and O(N(2-1/Delta)log(1/Delta)N) edges, with N = [B`n] for some constant B` that depends only on Delta. Consequently, the so-called size-Ramsey number of any H with n vertices and maximum degree Delta is O(n(2-1/Delta)log(1/Delta)n) Our approach is based on random graphs; in fact, we show that the classical Erdos-Renyi random graph with the numerical parameters above satisfies a stronger partition property with high probability, namely, that any 2-colouring of its edges contains a monochromatic universal graph for the class of graphs on n vertices and maximum degree Delta. The main tool in our proof is the regularity method, adapted to a suitable sparse setting. The novel ingredient developed here is an embedding strategy that allows one to embed bounded degree graphs of linear order in certain pseudorandom graphs. Crucial to our proof is the fact that regularity is typically inherited at a scale that is much finer than the scale at which it is assumed. (C) 2011 Elsevier Inc. All rights reserved.

FROM TRISECTIONS IN MODULE CATEGORIES TO QUASI-DIRECTED COMPONENTS

In this paper, we define and study a special type of trisections in a module category, namely the compact trisections which characterize quasi-directed components. We apply this notion to the study of laura algebras and we use it to define a class of algebras with predictable Auslander-Reiten components.