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.

An algorithmic Friedman-Pippenger theorem on tree embeddings and applications

An (n, d)-expander is a graph G = (V, E) such that for every X subset of V with vertical bar X vertical bar <= 2n - 2 we have vertical bar Gamma(G)(X) vertical bar >= (d + 1) vertical bar X vertical bar. A tree T is small if it has at most n vertices and has maximum degree at most d. Friedman and Pippenger (1987) proved that any ( n; d)- expander contains every small tree. However, their elegant proof does not seem to yield an efficient algorithm for obtaining the tree. In this paper, we give an alternative result that does admit a polynomial time algorithm for finding the immersion of any small tree in subgraphs G of (N, D, lambda)-graphs Lambda, as long as G contains a positive fraction of the edges of Lambda and lambda/D is small enough. In several applications of the Friedman-Pippenger theorem, including the ones in the original paper of those authors, the (n, d)-expander G is a subgraph of an (N, D, lambda)-graph as above. Therefore, our result suffices to provide efficient algorithms for such previously non-constructive applications. As an example, we discuss a recent result of Alon, Krivelevich, and Sudakov (2007) concerning embedding nearly spanning bounded degree trees, the proof of which makes use of the Friedman-Pippenger theorem. We shall also show a construction inspired on Wigderson-Zuckerman expander graphs for which any sufficiently dense subgraph contains all trees of sizes and maximum degrees achieving essentially optimal parameters. Our algorithmic approach is based on a reduction of the tree embedding problem to a certain on-line matching problem for bipartite graphs, solved by Aggarwal et al. (1996).

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.

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.

Membranas biológicas homólogas preservadas em solução alcalina seguida de liofilização, glicerina a 98% e por liofilização para implantação em eqüinos

Objetivou-se, neste trabalho, avaliar as alterações físico-químicas proporcionadas pelo tratamento de centros tendinosos diafragmáticos homólogos em solução alcalina seguida de liofilização, para implantação na fáscia interna do músculo reto do abdome de eqüinos. As amostras foram tratadas em períodos de 24, 48, 72, 120 e 144 horas, liofilizadas e analisadas quanto à homogeneidade, flexibilidade e resistência à sutura das amostras. Posteriormente foram caracterizadas por calorimetria exploratória diferencial e microscopia eletrônica de varredura. Para a implantação nos eqüinos, foram utilizadas amostras tratadas por 72 horas seguidas de liofilização, amostras conservadas em glicerina 98% e amostras apenas liofilizadas, que foram retiradas após uma, nove e 18 semanas para avaliar a existência de aderências. Verificou-se que a homogeneidade e a flexibilidade são diretamente proporcionais ao aumento do tempo de tratamento em solução alcalina, enquanto que a resistência é inversamente proporcional ao aumento de tempo, sendo o tratamento por 72 horas intermediário para estas características. A calorimetria exploratória diferencial mostrou que o tratamento não desnatura o colágeno presente nas amostras. Na microscopia eletrônica de varredura, observou-se que o aumento de tempo de tratamento proporciona expansão de zonas menos densas do material. Em relação à formação de aderências, as amostras apenas liofilizadas apresentaram grau máximo na formação da classificação proposta, seguida pelas amostras conservadas em glicerina 98% com grau médio e as amostras tratadas em solução alcalina e liofilizadas, que foram classificadas em grau mínimo. Concluiu-se que o tratamento por 72 horas seria mais apropriado para implantação e que a integração tissular com a parede abdominal foi melhor em relação às amostras apenas liofilizadas e às conservadas em glicerina.

Influence of carbon source and inoculum type on anaerobic biomass adhesion on polyurethane foam in reactors fed with acid mine drainage

This paper analyzes the influence of carbon source and inoculum origin on the dynamics of biomass adhesion to an inert support in anaerobic reactors fed with acid mine drainage. Formic acid, lactic acid and ethanol were used as carbon sources. Two different inocula were evaluated: one taken from an UASB reactor and other from the sediment of a uranium mine. The values of average colonization rates and the maximum biomass concentration (C(max)) were inversely proportional to the number of carbon atoms in each substrate. The highest C(max) value (0.35 g TVS g(-1) foam) was observed with formic acid and anaerobic sludge as inoculum. Maximum colonization rates (v(max)) were strongly influenced by the type of inoculum when ethanol and lactic acid were used. For both carbon sources, the use of mine sediment as inoculum resulted in a v(max) of 0.013 g TVS g(-1) foam day(-1), whereas 0.024 g TVS g(-1) foam day(-1) was achieved with anaerobic sludge. (C) 2011 Elsevier Ltd. All rights reserved.

Growth and acidification performance of probiotics in pure culture and co-culture with Streptococcus thermophilus: The effect of inulin

Inulin was used as a prebiotic to improve the quality and consistency of skim milk fermented by co-cultures and pure Cultures of Lactobacillus acidophilus, Lactobacillus rhamnosus, Lactobacillus bulgaricus and Bifidobacterium lactis with Streptococcus thermophilus. We compared, either in the presence or absence of 4 g inulin/100 g, the results of the main kinetic parameters, specifically the generation time (t(g)), the maximum acidification rate (V(max)). and the times to reach V(max) (t(max)), to attain pH 5.0 (t(pH5.0)) and to complete the fermentation (t(pH4.5)). Post-acidification, lactic acid formation and cell counts were also determined and compared, either 1 day after the fermentation was complete or after 7 day storage at 4 degrees C. In general, inulin addition to the milk increased in co-cultures V(max), decreased t(max), t(g) and t(pH4.5), favored post-acidification, exerted a bifidogenic effect, and preserved almost intact cell viability during storage. In addition, S. thermophilus was shown to stimulate the metabolism of the other lactic bacteria. Contrary to co-cultures, most of the effects in pure Cultures were not statistically significant. The most important aspect of this paper is the use of the generation time as a toot to investigate the microbial response to inulin addition. (c) 2009 Elsevier Ltd. All rights reserved.

Effect of inulin on growth and acidification performance of different probiotic bacteria in co-cultures and mixed culture with Streptococcus thermophilus

Inulin was used as a prebiotic to improve the quality and consistency of skim milk fermented by Lactobacillus acidophilus (La), Lactobacillus rhamnosus (Lr), Lactobacillus bulgaricus (Lb) and Bifidobacterium lactis (BI) with Streptococcus thermophilus (St), either in binary co-cultures or in cocktail containing all microorganisms. We compared, either in the presence of 40 mg inulin g(-1) or not, the results of the maximum acidification rate (V(max)) and the times to reach it (t(max)), to reach pH 5.0 (t(PH5.0)) and to complete the fermentation (t(f)). Post-acidification, lactic acid formation and cell counts were also compared after either 1 day (D1) or 7 days of storage at 4 degrees C (N). In co-culture, inulin addition to the milk increased V(max), decreased t(max) and t(f), favored post-acidification and exerted a bifidogenic effect. S. thermophilus proved to stimulate the metabolism of the other lactic bacteria and enhanced the product features. After D7, a significant prebiotic effect of inulin was observed in all co-cultures. Either after D1 or D7, the enumerations of Lr and BI in mixed culture markedly decreased compared to their respective co-cultures because of greater competition for the same substrates. (C) 2008 Elsevier Ltd. All rights reserved.

Bioequivalence study of two oral formulations of cefadroxil in healthy volunteers

Two different cefadroxil (CAS 50370-12-2) formulations were evaluated for their relative bioavailability in 24 healthy volunteers who received a single 500 mg oral dose of each preparation. An open, randomized clinical trial designed as a two-period crossover study with a 7-day washout period between doses was employed. Plasma samples for assessments of their cefadroxil concentration by HPLC-UV were obtained over 8 h after administration. Values of 48.94 +/- 10.18 mu g . h/ml for test, and 48.51 +/- 9.02 mu g . h/ml for the reference preparation AUC(0-t) demonstrate a nearly identical extend of drug absorption. Maximum plasma concentration C-max of 16.04 +/- 4.94 mu g/ml and 16.01 +/- 4.02 mu g/ml achieved for the test and reference preparations did not differ significantly. The parametric 90% confidence intervals (CI) of the mean of the difference (test-reference) between log-transformed values of the two formulations were 96.80% to 104.51% and 92.01% to 107.00% for AUC(0-t) and C-max, respectively. Since for both AUC(0-t) or C-max the 90% CI values are within the interval proposed by the Food and Drug Administration, the test product is bioequivalent to the reference product for both the rate and extent of absorption after single dose administration.

Elastic modulus of posts and the risk of root fracture

The definition of an optimal elastic modulus for a post is controversial. This work hypothesized that the influence of the posts` elastic modulus on dentin stress concentration is dependent on the load direction. The objective was to evaluate, using finite element analysis, the maximum principal stress (sigma(max)) on the root, using posts with different elastic modulus submitted to different loading directions. Nine 3D models were built, representing the dentin root, gutta-percha, a conical post and the cortical bone. The softwares used were: MSC.PATRAN2005r2 (preprocessing) and MSC.Marc2005r2 (processing). Load of 100 N was applied, varying the directions (0 degrees, 45 degrees and 90 degrees) in relation to the post`s long axis. The magnitude and direction of the sigma(max) were recorded. At the 45 degrees and 90 degrees loading, the highest values of sigma(max) were recorded for the lowest modulus posts, on the cervical region, with a direction that suggests debonding of the post. For the 0 degrees loading, the highest values of sigma(max) were recorded for higher modulus posts, on the apical region, and the circumferential direction suggests vertical root fracture. The hypothesis was accepted: the effect of the elastic modulus on the magnitude and direction of the sigma(max) generated on the root was dependent on the loading direction.

The suitability of different FEA models for studying root fractures caused by wedge effect

Finite element analysis (FEA) utilizing models with different levels of complexity are found in the literature to study the tendency to vertical root fracture caused by post intrusion (""wedge effect""). The objective of this investigation was to verify if some simplifications used in bi-dimensional FEA models are acceptable regarding the analysis of stresses caused by wedge effect. Three plane strain (PS) and two axisymmtric (Axi) models were studied. One PS model represented the apical third of the root entirely, in dentin (PS-nG). The other models included gutta-percha in the apical third, and differed regarding dentin-post relationship: bonded (PS-B and Axi-B) or nonbonded (PS-nB and Axi-nB). Mesh discretization and material properties were similar for all cases. Maximum principal stress (sigma(max)) was analyzed as a response to a 165 N longitudinal load. Stress magnitude and orientation varied widely (PS-nG: 10.3 MPa; PS-B: 0.8 MPa; PS-nB: 10.4 MPa; Axi-13: 0.2 MPa, Axi-nB: 10.8 MPa). Axi-nB was the only model where all (sigma(max) vectors at the apical third were perpendicular to the model plane. Therefore, it is adequate to demonstrate the tendency to vertical root fractures caused by wedge effect. Axi-13 showed only part of the (sigma(max) perpendicular to the model plane while PS models showed sigma(max) on the model plane. In these models, sigma(max) orientation did not represent a situation where vertical root fracture would occur due to wedge effect. Adhesion between post and dentin significantly reduced (c) 2007 Wiley Periodicals, Inc.

Hypotheses testing for structural calibration model

The main objective of this paper is to discuss maximum likelihood inference for the comparative structural calibration model (Barnett, in Biometrics 25:129-142, 1969), which is frequently used in the problem of assessing the relative calibrations and relative accuracies of a set of p instruments, each designed to measure the same characteristic on a common group of n experimental units. We consider asymptotic tests to answer the outlined questions. The methodology is applied to a real data set and a small simulation study is presented.

Acetylation of cellulose in LiCl-N,N-dimethylacetamide: first report on the correlation between the reaction efficiency and the aggregation number of dissolved cellulose

The acylation of three cellulose samples by acetic anhydride, Ac(2)O, in the solvent system LiCl/N,N-dimethylacetamide, DMAc (4 h, 110 A degrees C), has been revisited in order to investigate the dependence of the reaction efficiency on the structural characteristics of cellulose, and its aggregation in solution. The cellulose samples employed included microcrystalline, MCC; mercerized cotton linters, M-cotton, and mercerized sisal, M-sisal. The reaction efficiency expresses the relationship between the degree of substitution, DS, of the ester obtained, and the molar ratio Ac(2)O/AGU (anhydroglucose unit of the biopolymer); 100% efficiency means obtaining DS = 3 at Ac(2)O/AGU = 3. For all celluloses, the dependence of DS on Ac(2)O/AGU is described by an exponential decay equation: DS = DS(o) - Ae(-[(Ac2O/AGU)/B]); (A) and (B) are regression coefficients, and DS(o) is the calculated maximum degree of substitution, achieved under the conditions of each experiment. Values of (B) are clearly dependent on the cellulose employed: B((M-cotton)) > B((M-sisal)) > B((MCC)); they correlate qualitatively with the degree of polymerization of cellulose, and linearly with the aggregation number, N(agg), of the dissolved biopolymer, as calculated from static light scattering measurements: (B) = 1.709 + 0.034 N(agg). To our knowledge, this is the first report on the latter correlation; it shows the importance of the physical state of dissolved cellulose, and serves to explain, in part, the need to use distinct reaction conditions for MCC and fibrous celluloses, in particular Ac(2)O/AGU, time, temperature.

Adaptive Approach for a Maximum Entropy Algorithm in Ecological Niche Modeling

This paper presents an Adaptive Maximum Entropy (AME) approach for modeling biological species. The Maximum Entropy algorithm (MaxEnt) is one of the most used methods in modeling biological species geographical distribution. The approach presented here is an alternative to the classical algorithm. Instead of using the same set features in the training, the AME approach tries to insert or to remove a single feature at each iteration. The aim is to reach the convergence faster without affect the performance of the generated models. The preliminary experiments were well performed. They showed an increasing on performance both in accuracy and in execution time. Comparisons with other algorithms are beyond the scope of this paper. Some important researches are proposed as future works.

Finite element and dimensional analysis algorithm for the prediction of mechanical properties of bulk materials and thin films

In this work, the applicability of a new algorithm for the estimation of mechanical properties from instrumented indentation data was studied for thin films. The applicability was analyzed with the aid of both three-dimensional finite element simulations and experimental indentation tests. The numerical approach allowed studying the effect of the substrate on the estimation of mechanical properties of the film, which was conducted based on the ratio h(max)/l between maximum indentation depth and film thickness. For the experimental analysis, indentation tests were conducted on AISI H13 tool steel specimens, plasma nitrated and coated with TiN thin films. Results have indicated that, for the conditions analyzed in this work, the elastic deformation of the substrate limited the extraction of mechanical properties of the film/substrate system. This limitation occurred even at low h(max)/l ratios and especially for the estimation of the values of yield strength and strain hardening exponent. At indentation depths lower than 4% of the film thickness, the proposed algorithm estimated the mechanical properties of the film with accuracy. Particularly for hardness, precise values were estimated at h(max)/l lower than 0.1, i.e. 10% of film thickness. (C) 2010 Published by Elsevier B.V.