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.

CENTRAL UNITS IN METACYCLIC INTEGRAL GROUP RINGS

In this article, we give a method to compute the rank of the subgroup of central units of ZG, for a finite metacyclic group, G, by means of Q-classes and R-classes. Then we construct a multiplicatively independent set u subset of Z(U(ZC(p,q))) and by applying our results, we prove that u generates a subgroup of finite index.

Robust linear mixed models with skew-normal independent distributions from a Bayesian perspective

Linear mixed models were developed to handle clustered data and have been a topic of increasing interest in statistics for the past 50 years. Generally. the normality (or symmetry) of the random effects is a common assumption in linear mixed models but it may, sometimes, be unrealistic, obscuring important features of among-subjects variation. In this article, we utilize skew-normal/independent distributions as a tool for robust modeling of linear mixed models under a Bayesian paradigm. The skew-normal/independent distributions is an attractive class of asymmetric heavy-tailed distributions that includes the skew-normal distribution, skew-t, skew-slash and the skew-contaminated normal distributions as special cases, providing an appealing robust alternative to the routine use of symmetric distributions in this type of models. The methods developed are illustrated using a real data set from Framingham cholesterol study. (C) 2009 Elsevier B.V. All rights reserved.

Correlation of the highest-energy cosmic rays with the positions of nearby active galactic nuclei

Data collected by the Pierre Auger Observatory provide evidence for anisotropy in the arrival directions of the cosmic rays with the highest-energies, which are correlated with the positions of relatively nearby active galactic nuclei (AGN) [Pierre Auger Collaboration, Science 318 (2007) 938]. The correlation has maximum significance for cosmic rays with energy greater than similar to 6 x 10(19) eV and AGN at a distance less than similar to 75 Mpc. We have confirmed the anisotropy at a confidence level of more than 99% through a test with parameters specified a priori, using an independent data set. The observed correlation is compatible with the hypothesis that cosmic rays with the highest-energies originate from extra-galactic sources close enough so that their flux is not significantly attenuated by interaction with the cosmic background radiation (the Greisen-Zatsepin-Kuz`min effect). The angular scale of the correlation observed is a few degrees, which suggests a predominantly light composition unless the magnetic fields are very weak outside the thin disk of our galaxy. Our present data do not identify AGN as the sources of cosmic rays unambiguously, and other candidate sources which are distributed as nearby AGN are not ruled out. We discuss the prospect of unequivocal identification of individual sources of the highest-energy cosmic rays within a few years of continued operation of the Pierre Auger Observatory. (C) 2008 Elsevier B.V. All rights reserved.

Texture analysis based on maximum contrast walker

Recently, the deterministic tourist walk has emerged as a novel approach for texture analysis. This method employs a traveler visiting image pixels using a deterministic walk rule. Resulting trajectories provide clues about pixel interaction in the image that can be used for image classification and identification tasks. This paper proposes a new walk rule for the tourist which is based on contrast direction of a neighborhood. The yielded results using this approach are comparable with those from traditional texture analysis methods in the classification of a set of Brodatz textures and their rotated versions, thus confirming the potential of the method as a feasible texture analysis methodology. (C) 2010 Elsevier B.V. All rights reserved.

Continuous GRASP with a local active-set method for bound-constrained global optimization

Global optimization seeks a minimum or maximum of a multimodal function over a discrete or continuous domain. In this paper, we propose a hybrid heuristic-based on the CGRASP and GENCAN methods-for finding approximate solutions for continuous global optimization problems subject to box constraints. Experimental results illustrate the relative effectiveness of CGRASP-GENCAN on a set of benchmark multimodal test functions.

Improved maximum likelihood estimators in a heteroskedastic errors-in-variables model

This paper develops a bias correction scheme for a multivariate heteroskedastic errors-in-variables model. The applicability of this model is justified in areas such as astrophysics, epidemiology and analytical chemistry, where the variables are subject to measurement errors and the variances vary with the observations. We conduct Monte Carlo simulations to investigate the performance of the corrected estimators. The numerical results show that the bias correction scheme yields nearly unbiased estimates. We also give an application to a real data set.