An improved bit parallel exact maximum clique algorithm

This paper describes new improvements for BB-MaxClique (San Segundo et al. in Comput Oper Resour 38(2):571–581, 2011 ), a leading maximum clique algorithm which uses bit strings to efficiently compute basic operations during search by bit masking. Improvements include a recently described recoloring strategy in Tomita et al. (Proceedings of the 4th International Workshop on Algorithms and Computation. Lecture Notes in Computer Science, vol 5942. Springer, Berlin, pp 191–203, 2010 ), which is now integrated in the bit string framework, as well as different optimization strategies for fast bit scanning. Reported results over DIMACS and random graphs show that the new variants improve over previous BB-MaxClique for a vast majority of cases. It is also established that recoloring is mainly useful for graphs with high densities.

Watching subgraphs to improve efficiency in maximum clique search

This paper describes a new technique referred to as watched subgraphs which improves the performance of BBMC, a leading state of the art exact maximum clique solver (MCP). It is based on watched literals employed by modern SAT solvers for boolean constraint propagation. In efficient SAT algorithms, a list of clauses is kept for each literal (it is said that the clauses watch the literal) so that only those in the list are checked for constraint propagation when a (watched) literal is assigned during search. BBMC encodes vertex sets as bit strings, a bit block representing a subset of vertices (and the corresponding induced subgraph) the size of the CPU register word. The paper proposes to watch two subgraphs of critical sets during MCP search to efficiently compute a number of basic operations. Reported results validate the approach as the size and density of problem instances rise, while achieving comparable performance in the general case.

Solving Maximum Clique Problem for Protein Structure Similarity

Computing the similarity between two protein structures is a crucial task in molecular biology, and has been extensively investigated. Many protein structure comparison methods can be modeled as maximum weighted clique problems in specific k-partite graphs, referred here as alignment graphs. In this paper we present both a new integer programming formulation for solving such clique problems and a dedicated branch and bound algorithm for solving the maximum cardinality clique problem. Both approaches have been integrated in VAST, a software for aligning protein 3D structures largely used in the National Center for Biotechnology Information, an original clique solver which uses the well known Bron and Kerbosch algorithm (BK). Our computational results on real protein alignment instances show that our branch and bound algorithm is up to 116 times faster than BK.

Graph-based User Scheduling for MIMO LEO-based Satellite Communication Systems

The study of the user scheduling problem in a Low Earth Orbit (LEO) Multi-User MIMO system is the objective of this thesis. With the application of cutting-edge digital beamforming algorithms, a LEO satellite with an antenna array and a large number of antenna elements can provide service to many user terminals (UTs) in full frequency reuse (FFR) schemes. Since the number of UTs on-ground are many more than the transmit antennas on the satellite, user scheduling is necessary. Scheduling can be accomplished by grouping users into different clusters: users within the same cluster are multiplexed and served together via Space Division Multiple Access (SDMA), i.e., digital beamforming or Multi-User MIMO techniques; the different clusters of users are then served on different time slots via Time Division Multiple Access (TDMA). The design of an optimal user grouping strategy is known to be an NP-complete problem which can be solved only through exhaustive search. In this thesis, we provide a graph-based user scheduling and feed space beamforming architecture for the downlink with the aim of reducing user inter-beam interference. The main idea is based on clustering users whose pairwise great-circle distance is as large as possible. First, we create a graph where the users represent the vertices, whereas an edge in the graph between 2 users exists if their great-circle distance is above a certain threshold. In the second step, we develop a low complex greedy user clustering technique and we iteratively search for the maximum clique in the graph, i.e., the largest fully connected subgraph in the graph. Finally, by using the 3 aforementioned power normalization techniques, a Minimum Mean Square Error (MMSE) beamforming matrix is deployed on a cluster basis. The suggested scheduling system is compared with a position-based scheduler, which generates a beam lattice on the ground and randomly selects one user per beam to form a cluster.

Approximation algorithms and hardness results for the clique packing problem

For a fixed family F of graphs, an F-packing in a graph G is a set of pairwise vertex-disjoint subgraphs of G, each isomorphic to an element of F. Finding an F-packing that maximizes the number of covered edges is a natural generalization of the maximum matching problem, which is just F = {K(2)}. In this paper we provide new approximation algorithms and hardness results for the K(r)-packing problem where K(r) = {K(2), K(3,) . . . , K(r)}. We show that already for r = 3 the K(r)-packing problem is APX-complete, and, in fact, we show that it remains so even for graphs with maximum degree 4. On the positive side, we give an approximation algorithm with approximation ratio at most 2 for every fixed r. For r = 3, 4, 5 we obtain better approximations. For r = 3 we obtain a simple 3/2-approximation, achieving a known ratio that follows from a more involved algorithm of Halldorsson. For r = 4, we obtain a (3/2 + epsilon)-approximation, and for r = 5 we obtain a (25/14 + epsilon)-approximation. (C) 2008 Elsevier B.V. All rights reserved.

Didanosine-loaded Chitosan Microspheres Optimized By Surface-response Methodology: A Modified Maximum Likelihood Classification" Approach Formulation For Reverse Transcriptase Inhibitors."

Didanosine-loaded chitosan microspheres were developed applying a surface-response methodology and using a modified Maximum Likelihood Classification. The operational conditions were optimized with the aim of maintaining the active form of didanosine (ddI), which is sensitive to acid pH, and to develop a modified and mucoadhesive formulation. The loading of the drug within the chitosan microspheres was carried out by ionotropic gelation technique with sodium tripolyphosphate (TPP) as cross-linking agent and magnesium hydroxide (Mg(OH)2) to assure the stability of ddI. The optimization conditions were set using a surface-response methodology and applying the Maximum Likelihood Classification, where the initial chitosan concentration, TPP and ddI concentration were set as the independent variables. The maximum ddI-loaded in microspheres (i.e. 1433mg of ddI/g chitosan), was obtained with 2% (w/v) chitosan and 10% TPP. The microspheres depicted an average diameter of 11.42μm and ddI was gradually released during 2h in simulated enteric fluid.

Maximum inhibitory dilution of mouthwashes containing chlorhexidine and polyhexamethylene biguanide against salivary staphylococcus aureus

OBJECTIVE: The aim of the present study was to determine the in vitro maximum inhibitory dilution (MID) of two chlorhexidinebased oral mouthwashes (CHX): Noplak®, Periogard®, and one polyhexamethylene biguanide-based mouthwash (PHMB): Sanifill Premium® against 28 field Staphylococcus aureus strains using the agar dilution method. MATERIALS AND METHODS: For each product, decimal dilutions ranging from 1/10 to 1/655,360 were prepared in distilled water and added to Mueller Hinton Agar culture medium. After homogenization, the culture medium was poured onto Petri dishes. Strains were inoculated using a Steers multipoint inoculator and dishes were incubated at 37ºC for 24hours. For reading, MID was considered as the maximum dilution of the mouthwash still capable of inhibiting microbial growth. RESULTS: Sanifill Premium® inhibited the growth of all strains at 1/40 dilution and of 1 strain at 1/80 dilution. Noplak® inhibited the growth of 23 strains at 1/640 dilution and of all 28 strains at 1/320 dilution. Periogard® showed inhibited growth of 7 strains at 1/640 dilution and of all 28 strains at 1/320 dilution. Data were submitted to Kruskal-Wallis statistical test, showing significant differences between the mouthwashes evaluated (p<0.05). No significant difference was found between Noplak® and Periogard® (p>0.05). Sanifill Premium® was the least effective (p<0.05). CONCLUSION: It was concluded that CHX-based mouthwashes present better antimicrobial activity against S. Aureus than the PHMB-based mouthwash.

Determination of the maximum inhibitory dilution of cetylpyridinium chloride-based mouthwashes against staphylococcus aureus: an in vitro study

The aim of this in vitro study was to determine the maximum inhibitory dilution (MID) of four cetylpyridinium chloride (CPC)-based mouthwashes: CPC+Propolis, CPC+Malva, CPC+Eucaliptol+Juá+Romã+Propolis (Natural Honey®) and CPC (Cepacol®), against 28 Staphylococcus aureus field strains, using the agar dilution method. Decimal dilutions ranging from 1/10 to 1/655,360 were prepared and added to Mueller Hinton Agar. Strains were inoculated using Steers multipoint inoculator. The inocula were seeded onto the surface of the culture medium in Petri dishes containing different dilutions of the mouthwashes. The dishes were incubated at 37ºC for 24 h. For readings, the MID was considered as the maximum dilution of mouthwash still capable of inhibiting microbial growth. The obtained data showed that CPC+Propolis had antimicrobial activity against 27 strains at 1/320 dilution and against all 28 strains at 1/160 dilution, CPC+Malva inhibited the growth of all 28 strains at 1/320 dilution, CPC+Eucaliptol+Juá+Romã+Propolis inhibited the growth of 2 strains at 1/640 dilution and all 28 strains at 1/320 dilution, and Cepacol® showed antimicrobial activity against 3 strains at 1/320 dilution and against all 28 strains at 1/160 dilution. Data were submitted to Kruskal-Wallis test, showing that the MID of Cepacol® was lower than that determined for the other products (p<0.05). In conclusion, CPC-mouthwashes showed antimicrobial activity against S. aureus and the addition of other substances to CPC improved its antimicrobial effect.

Características agronômicas do Panicum maximum cv. "Mombaça" submetido a níveis crescentes de fósforo

O objetivo deste experimento foi avaliar o efeito da adição de doses crescentes de P2O5 sobre a altura do dossel, o número de perfilhos e a produção de matéria seca de folhas e de colmos do capim-Mombaça, em diferentes idades. Foi conduzido um experimento implantado em um Nitossolo Vermelho Eutrófico. O delineamento experimental usado foi o de blocos completos casualizados, com quatro repetições, cinco doses de P2O5 (30, 60, 90, 120 e 150kg ha-1) e uma testemunha. Para a primeira e segunda coletas, observou-se o efeito linear do fósforo sobre o perfilhamento. Para a terceira e quarta coletas, os dados ajustaram-se ao modelo quadrático. A participação das lâminas foliares na matéria seca da parte aérea diminuiu com as doses de P2O5. Por outro lado, a participação de colmos aumentou com as doses de P2O5. A produção de matéria seca (MS) da parte aérea para primeira, segunda e terceira coletas respondeu de forma linear à aplicação de P2O5 observando-se um aumento estimado de 7, 15 e 19kg ha-1 de MS por kg ha-1 de P2O5, respectivamente. Para a quarta coleta, os dados ajustaram-se ao modelo quadrático de regressão, sendo a máxima produção, 8,3Mg ha-1 de MS, obtida com a aplicação de 103kg ha-1 de P2O5.

Herbage accumulation, growth and structural characteristics of Mombasa grass (Panicum maximum Jacq.) harvested at different cutting intervals

The objective of the present study was to evaluate herbage accumulation, morphological composition, growth rate and structural characteristics in Mombasa grass swards subject to different cutting intervals (3, 5 and 7 wk) during the rainy and dry seasons of the year. Treatments were assigned to experimental units (17.5 m(2)) according to a complete randomised block design, with four replicates. Herbage accumulation was greater in the rainy than in the dry season (83 and 17%, respectively). Herbage accumulation (24,300 kg DM ha(-1)), average growth rate (140 kg DM ha(-1) d(-1)) and sward height (111 cm) were highest in the 7 wk cutting interval, but leaf proportion (56%), leaf:stem (1.6) and leaf:non leaf (1.3) ratios decreased. Herbage accumulation, morphological composition and sward structure of Mombasa grass sward may be manipulated through defoliation frequency. The highest leaf proportion was recorded in the 3-wk cutting interval. Longer cutting intervals affected negatively sward structure, with potential negative effects on utilization efficiency, animal intake and performance.

Condylar displacement between centric relation and maximum intercuspation in symptomatic and asymptomatic individuals

Objective: To measure condylar displacement between centric relation (CR) and maximum intercuspation (MIC) in symptomatic and asymptomatic subjects. Materials and Methods: The sample comprised 70 non-deprogrammed individuals, divided equally into two groups, one symptomatic and the other asymptomatic, grouped according to the research diagnostic criteria for temporomandibular disorders (RDC/TMD). Condylar displacement was measured in three dimensions with the condylar position indicator (CPI) device. Dahlberg's index, intraclass correlation coefficient, repeated measures analysis of variance, analysis of variance, and generalized estimating equations were used for statistical analysis. Results: A greater magnitude of difference was observed on the vertical plane on the left side in both symptomatic and asymptomatic individuals (P = .033). The symptomatic group presented higher measurements on the transverse plane (P = .015). The percentage of displacement in the mesial direction was significantly higher in the asymptomatic group than in the symptomatic one (P = .049). Both groups presented a significantly higher percentage of mesial direction on the right side than on the left (P = .036). The presence of bilateral condylar displacement (left and right sides) in an inferior and distal direction was significantly greater in symptomatic individuals (P = .012). However, no statistical difference was noted between genders. Conclusion: Statistically significant differences between CR and MIC were quantifiable at the condylar level in asymptomatic and symptomatic individuals. (Angle Orthod. 2010;80:835-842.)

Measurement of the depth of maximum of extensive air showers above 10(18) eV

We describe the measurement of the depth of maximum, X(max), of the longitudinal development of air showers induced by cosmic rays. Almost 4000 events above 10(18) eV observed by the fluorescence detector of the Pierre Auger Observatory in coincidence with at least one surface detector station are selected for the analysis. The average shower maximum was found to evolve with energy at a rate of (106 +/- 35-21) g/cm(2)/decade below 10(18.24) +/- (0.05) eV, and d24 +/- 3 g/cm(2)/ecade above this energy. The measured shower-to-shower fluctuations decrease from about 55 to 26 g/cm(2). The interpretation of these results in terms of the cosmic ray mass composition is briefly discussed.

FORAMINIFERAL RECORD OF CHANGES IN SUMMER MONSOON PRECIPITATION AT THE SOUTHEASTERN BRAZILIAN CONTINENTAL MARGIN SINCE THE LAST GLACIAL MAXIMUM

Changes in the oxygen isotopic composition of the planktonic foraminifer Globigerinoides ruber and in the foraminifera faunal composition in a core retrieved from the southeastern Brazilian continental margin were used to infer past changes in the hydrological balance and monsoon precipitation in the western South Atlantic since the Last Glacial Maximum (LGM). The results suggest a first-order orbital (precessional) control on the South American Monsoon precipitation. This agrees with previous studies based on continental proxies except for LGM estimates provided by pollen records. The causes for this disagreement are discussed.

Last glacial maximum (LGM) vegetation changes in the Atlantic Forest, southeastern Brazil

This study was carried out in a continental Atlantic Forest located in the southern region of Sao Paulo State, southeastern Brazil. The aim of the study was to evaluate the vegetation dynamics in similar to 70 km forest ecosystem transect that occurred during the late Pleistocene and Holocene in this region, using the stable carbon isotopes (delta C-13) analysis on soil organic matter (SOM) and the C-14 dating of buried charcoal fragments and the humin fraction of SOM. The isotope data (delta C-13) of SOM in the deeper horizons, indicating the presence of more open vegetation than the present, with a probable mixture of C-3 and C-4 plants, suggesting the presence of a drier climate in the period of similar to 20 ka to similar to 16-14 ka BP. From similar to 16 to 14 ka BP to the present, a significant predominance Of C3 plants was observed, indicating an expansion of the forest, probably associated with the presence of a more humid climate than the previous period. The results indicated the presence of open vegetation during the late glacial, probably associated with a drier period, also observed in other regions of Brazil. The Atlantic Forest ecosystem seems to have developed at least since the early Holocene in Southeastern Brazil. (c) 2007 Elsevier Ltd and INQUA. All rights reserved.

The influence of microstructure on the maximum load and fracture energy of refractory castables

Refractory castables are composed of fractions of fine to fairly coarse particles. The fine fraction is constituted primarily of raw materials and calcium aluminate cement, which becomes hydrated, forming chemical bonds that stiffen the concrete during the curing process. The present study focused on an evaluation of several characteristics of two refractory castables with similar chemical compositions but containing aggregates of different sizes. The features evaluated were the maximum load, the fracture energy, and the ""relative crack-propagation work"" of the two castables heat-treated at 110, 650, 1100 and 1550 degrees C. The results enabled us to draw the following conclusions: the heat treatment temperature exerts a significant influence on the matrix/aggregate interaction, different microstructures form in the castables with temperature, and a relationship was noted between the maximum load and the fracture energy. (C) 2009 Elsevier Ltd and Techna Group S.r.l. All rights reserved.