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

On the k-restricted structure ratio in planar and outerplanar graphs

A planar k-restricted structure is a simple graph whose blocks are planar and each has at most k vertices. Planar k-restricted structures are used by approximation algorithms for Maximum Weight Planar Subgraph, which motivates this work. The planar k-restricted ratio is the infimum, over simple planar graphs H, of the ratio of the number of edges in a maximum k-restricted structure subgraph of H to the number edges of H. We prove that, as k tends to infinity, the planar k-restricted ratio tends to 1/2. The same result holds for the weighted version. Our results are based on analyzing the analogous ratios for outerplanar and weighted outerplanar graphs. Here both ratios tend to 1 as k goes to infinity, and we provide good estimates of the rates of convergence, showing that they differ in the weighted from the unweighted case.

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.

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.

Integral group ring of the Suzuki sporadic simple group

Using the Luthar-Passi method, we investigate the classical Zassenhaus conjecture for the normalized unit group of the integral group ring of the Suzuki sporadic simple group Suz. As a consequence, for this group we confirm the Kimmerle`s conjecture on prime graphs.

Geodesics and Almost Geodesic Cycles in Random Regular Graphs

A geodesic in a graph G is a shortest path between two vertices of G. For a specific function e(n) of n, we define an almost geodesic cycle C in G to be a cycle in which for every two vertices u and v in C, the distance d(G)(u, v) is at least d(C)(u, v) - e(n). Let omega(n) be any function tending to infinity with n. We consider a random d-regular graph on n vertices. We show that almost all pairs of vertices belong to an almost geodesic cycle C with e(n)= log(d-1)log(d-1) n+omega(n) and vertical bar C vertical bar =2 log(d-1) n+O(omega(n)). Along the way, we obtain results on near-geodesic paths. We also give the limiting distribution of the number of geodesics between two random vertices in this random graph. (C) 2010 Wiley Periodicals, Inc. J Graph Theory 66: 115-136, 2011

Fracture strength of teeth restored with ceramic inlays and overlays

This study evaluated the fracture strength of teeth restored with bonded ceramic inlays and overlays compared to sound teeth. Thirty sound human maxillary premolars were assigned to 3 groups: 1- sound/unprepared (control); 2- inlays and 3- overlays. The inlay cavity design was Class II MOD preparation with an occlusal width of 1/2 of the intercuspal distance. The overlay cavity design was similar to that of the inlay group, except for buccal and palatal cusp coverage The inlay and overlay groups were restored with feldspathic porcelain bonded with adhesive cement. The specimens were subjected to a compressive load until fracture. Data were analyzed statistically by the Kruskal-Wallis test at 5% significance level. The fracture strength means (KN) were: Sound/unprepared group = 1.17, Inlay group= 1.17, and Overlay group = 1.14. There were no statistically significant differences (p>0.05) among the groups. For inlays and overlays, the predominant fracture mode involved fragments of one cusp (70% of simple fractures). The fracture strength of teeth restored with inlay and overlay ceramics with cusp coverage was similar to that of intact teeth.

Rhinometric evaluation of nasal cavity geometry and its relation to the upper arch transverse distance

The objective of this study was to evaluate children's respiratory patterns in the mixed dentition, by means of acoustic rhinometry, and its relation to the upper arch width development. Fifty patients were examined, 25 females and 25 males with mean age of eight years and seven months. All of them were submitted to acoustic rhinometry and upper and lower arch impressions to obtain plaster models. The upper arch analysis was accomplished by measuring the interdental transverse distance of the upper teeth, deciduous canines (measurement 1), deciduous first molars (measurement 2), deciduous second molars (measurement 3) and the first molars (measurement 4). The results showed that an increased left nasal cavity area in females means an increased interdental distance of the deciduous first molars and deciduous second molars and an increased interdental distance of the deciduous canines, deciduous first and second molars in males. It was concluded that there is a correlation between the nasal cavity area and the upper arch transverse distance in the anterior and mid maxillary regions for both genders.

Modelagem dos processos de remoção sulfato e dióxido de enxofre presente no particulado em diferentes localidades da região metropolitana de São Paulo

This article deals with the scavenging processes modeling of the particulate sulfate and the gas sulfur dioxide, emphasizing the synoptic conditions at different sampling sites in order to verify the domination of the in-cloud or below-cloud scavenging processes in the Metropolitan Area of São Paulo (RMSP). Three sampling sites were chosen: GV (Granja Viana) at RMSP surroundings, IAG-USP and Mackenzie (RMSP center). Basing on synoptic conditions, it was chosen a group of events where the numerical modeling, a simple scavenging model, was used. These synoptic conditions were usually convective cloud storms, which are usual at RMSP. The results show that the in-cloud processes were dominant (80%) for sulfate/sulfur dioxide scavenging processes, with below-cloud process indicating around 20% of the total. Clearly convective events, with total rainfall higher than 20 mm, are better modeled than the stratiform events, with correlation coefficient of 0.92. There is also a clear association with events presenting higher rainfall amount and the ratio between modeled and observed data set with correlation coefficient of 0.63. Additionally, the suburb sampling site, GV, as expected due to the pollution source distance, presents in general smaller amount of rainwater sulfate (modeled and observed) than the center sampling site, Mackenzie, where the characterization event explains partially the rainfall concentration differences.

Influence of separate and mixed experimental designs on reaction times to two simple visual stimuli

Testing contexts have been shown to critically influence experimental results in psychophysical studies. One of these contexts that show important modulation of the behavioral effects of different stimulatory conditions is the separate (blocked) or mixed presentation of these stimulatory conditions. The study presents evidence that the apparent discriminabilities of two target stimuli can change according to which of these two testing contexts is used. A cross inside a ring and a vertical line inside a ring were presented as go stimuli in a go/no-go reaction time task. In one experiment, each of these stimuli was presented to a different group of volunteers and in another experiment they were presented to the same group of volunteers, randomly mixed in the blocks of trials. Similar reaction times were obtained for the two stimuli in the first experiment, and different reaction times (faster for the cross) in the second experiment. The latter result indicates that the two stimuli have different discriminabilities from the no-go stimulus; the cross having greater discriminability. This difference is however masked, presumably by the adoption of specific compensatory attentional sets, in a separate testing context.

Using sentinels to detect intersections of convex and nonconvex polygons

We describe finite sets of points, called sentinels, which allow us to decide if isometric copies of polygons, convex or not, intersect. As an example of the applicability of the concept of sentinel, we explain how they can be used to formulate an algorithm based on the optimization of differentiable models to pack polygons in convex sets. Mathematical subject classification: 90C53, 65K05.

Design, construction and evaluation of a simple pressurized solvent extraction system

This work describes the construction and testing of a simple pressurized solvent extraction (PSE) system. A mixture of acetone:water (80:20), 80 ºC and 103.5 bar, was used to extract two herbicides (Diuron and Bromacil) from a sample of polluted soil, followed by identification and quantification by high-performance liquid chromatography coupled with diode array detector (HPLC-DAD). The system was also used to extract soybean oil (70 ºC and 69 bar) using pentane. The extracted oil was weighed and characterized through the fatty acid methyl ester analysis (myristic (< 0.3%), palmitic (16.3%), stearic (2.8%), oleic (24.5%), linoleic (46.3%), linolenic (9.6%), araquidic (0.3%), gadoleic (< 0.3%), and behenic (0.3%) acids) using high-resolution gas chromatography with flame ionization detection (HRGC-FID). PSE results were compared with those obtained using classical procedures: Soxhlet extraction for the soybean oil and solid-liquid extraction followed by solid-phase extraction (SLE-SPE) for the herbicides. The results showed: 21.25 ± 0.36% (m/m) of oil in the soybeans using the PSE system and 21.55 ± 0.65% (m/m) using the soxhlet extraction system; extraction efficiency (recovery) of herbicides Diuron and Bromacil of 88.7 ± 4.5% and 106.6 ± 8.1%, respectively, using the PSE system, and 96.8 ± 1.0% and 94.2 ± 3.9%, respectively, with the SLP-SPE system; limit of detection (LOD) and limit of quantification (LOQ) for Diuron of 0.012 mg kg-1 and 0.040 mg kg-1, respectively; LOD and LOQ for Bromacil of 0.025 mg kg-1 and 0.083 mg kg-1, respectively. The linearity used ranged from 0.04 to 1.50 mg L-1 for Diuron and from 0.08 to 1.50 mg L-1 for Bromacil. In conclusion, using the PSE system, due to high pressure and temperature, it is possible to make efficient, fast extractions with reduced solvent consumption in an inert atmosphere, which prevents sample and analyte decomposition.

Evaluation of a simple hyphenated system for flow injection solid-phase pre-concentration and capillary electrophoresis

In this work, the development and evaluation of a hyphenated flow injection-capillary electrophoresis system with on-line pre-concentration is described. Preliminary tests were performed to investigate the influence of flow rates over the analytical signals. Results revealed losses in terms of sensitivity of the FIA-CE system when compared to the conventional CE system. To overcome signal decrease and to make the system more efficient, a lower flow rate was set and an anionic resin column was added to the flow manifold in order to pre-concentrate the analyte. The pre-concentration FIA-CE system presented a sensitivity improvement of about 660% and there was only a small increase of 8% in total peak dispersion. These results have confirmed the great potential of the proposed system for many analytical tasks especially for low concentration samples.

I2: uma molécula didática

Iodine vapor is a very suitable substance to learn about molecular energy levels and transitions, and to introduce spectroscopic techniques. As a diatomic molecule its spectra are relatively simple and allow straightforward treatment of the data leading to the potential energy curves and to quantum mechanics concepts. The overtone bands, in the resonance Raman scattering, and the band progressions, in the electronic spectra, play an important role in the calculation of the Morse potential curves for the fundamental and excited electronic state. A weaker chemical bond in the electronic excited state, compared to the fundamental state, is evidenced by the increase in the equilibrium interatomic distance. The resonance Raman scattering of I2 is highlighted due to its importance for obtaining the anharmonicity constant in the fundamental electronic state.

Development and validation of a simple and rapid capillary zone electrophoresis method for determination of nnrti nevirapine in pharmaceutical formulations

A simple and fast capillary zone electrophoresis (CZE) method has been developed and validated for quantification of a non-nucleoside reverse transcriptase inhibitor (NNRTI) nevirapine, in pharmaceuticals. The analysis was optimized using 10 mmol L-1 sodium phosphate buffer pH 2.5, +25 kV applied voltage, hydrodynamic injection 0.5 psi for 5 s and direct UV detection at 200 µm. Diazepam (50.0 µg mL-1) was used as internal standard. Under these conditions, nevirapine was analyzed in approximately less than 2.5 min. The analytical curve presented a coefficient of correlation of 0.9994. Limits of detection and quantification were 1.4 µg mL-1 and 4.3 µg mL-1, respectively. Intra- and inter-day precision expressed as relative standard deviations were 1.4% and 1.3%, respectively and the mean recovery was 100.81%. The active pharmaceutical ingredient was subjected to hydrolysis (acid, basic and neutral) and oxidative stress conditions. No interference of degradation products and tablet excipients were observed. This method showed to be rapid, simple, precise, accurate and economical for determination of nevirapine in pharmaceuticals and it is suitable for routine quality control analysis since CE offers benefits in terms of quicker method development and significantly reduced operating costs.