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

Performance results of running parallel applications on the InteGrade

The InteGrade middleware intends to exploit the idle time of computing resources in computer laboratories. In this work we investigate the performance of running parallel applications with communication among processors on the InteGrade grid. As costly communication on a grid can be prohibitive, we explore the so-called systolic or wavefront paradigm to design the parallel algorithms in which no global communication is used. To evaluate the InteGrade middleware we considered three parallel algorithms that solve the matrix chain product problem, the 0-1 Knapsack Problem, and the local sequence alignment problem, respectively. We show that these three applications running under the InteGrade middleware and MPI take slightly more time than the same applications running on a cluster with only LAM-MPI support. The results can be considered promising and the time difference between the two is not substantial. The overhead of the InteGrade middleware is acceptable, in view of the benefits obtained to facilitate the use of grid computing by the user. These benefits include job submission, checkpointing, security, job migration, etc. Copyright (C) 2009 John Wiley & Sons, Ltd.

Simple telemedicine for developing regions: Camera phones and paper-based microfluidic devices for real-time, off-site diagnosis

This article describes a prototype system for quantifying bioassays and for exchanging the results of the assays digitally with physicians located off-site. The system uses paper-based microfluidic devices for running multiple assays simultaneously, camera phones or portable scanners for digitizing the intensity of color associated with each colorimetric assay, and established communications infrastructure for transferring the digital information from the assay site to an off-site laboratory for analysis by a trained medical professional; the diagnosis then can be returned directly to the healthcare provider in the field. The microfluidic devices were fabricated in paper using photolithography and were functionalized with reagents for colorimetric assays. The results of the assays were quantified by comparing the intensities of the color developed in each assay with those of calibration curves. An example of this system quantified clinically relevant concentrations of glucose and protein in artificial urine. The combination of patterned paper, a portable method for obtaining digital images, and a method for exchanging results of the assays with off-site diagnosticians offers new opportunities for inexpensive monitoring of health, especially in situations that require physicians to travel to patients (e.g., in the developing world, in emergency management, and during field operations by the military) to obtain diagnostic information that might be obtained more effectively by less valuable personnel.