PARALLEL ALGORITHMS FOR MAXIMAL CLIQUES IN CIRCLE GRAPHS AND UNRESTRICTED DEPTH SEARCH

We present parallel algorithms on the BSP/CGM model, with p processors, to count and generate all the maximal cliques of a circle graph with n vertices and m edges. To count the number of all the maximal cliques, without actually generating them, our algorithm requires O(log p) communication rounds with O(nm/p) local computation time. We also present an algorithm to generate the first maximal clique in O(log p) communication rounds with O(nm/p) local computation, and to generate each one of the subsequent maximal cliques this algorithm requires O(log p) communication rounds with O(m/p) local computation. The maximal cliques generation algorithm is based on generating all maximal paths in a directed acyclic graph, and we present an algorithm for this problem that uses O(log p) communication rounds with O(m/p) local computation for each maximal path. We also show that the presented algorithms can be extended to the CREW PRAM model.

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.

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

Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation

We investigate several two-dimensional guillotine cutting stock problems and their variants in which orthogonal rotations are allowed. We first present two dynamic programming based algorithms for the Rectangular Knapsack (RK) problem and its variants in which the patterns must be staged. The first algorithm solves the recurrence formula proposed by Beasley; the second algorithm - for staged patterns - also uses a recurrence formula. We show that if the items are not so small compared to the dimensions of the bin, then these algorithms require polynomial time. Using these algorithms we solved all instances of the RK problem found at the OR-LIBRARY, including one for which no optimal solution was known. We also consider the Two-dimensional Cutting Stock problem. We present a column generation based algorithm for this problem that uses the first algorithm above mentioned to generate the columns. We propose two strategies to tackle the residual instances. We also investigate a variant of this problem where the bins have different sizes. At last, we study the Two-dimensional Strip Packing problem. We also present a column generation based algorithm for this problem that uses the second algorithm above mentioned where staged patterns are imposed. In this case we solve instances for two-, three- and four-staged patterns. We report on some computational experiments with the various algorithms we propose in this paper. The results indicate that these algorithms seem to be suitable for solving real-world instances. We give a detailed description (a pseudo-code) of all the algorithms presented here, so that the reader may easily implement these algorithms. (c) 2007 Elsevier B.V. All rights reserved.

Towards a maximal extension of Pelczynski`s decomposition method in Banach spaces

l Suppose that X, Y. A and B are Banach spaces such that X is isomorphic to Y E) A and Y is isomorphic to X circle plus B. Are X and Y necessarily isomorphic? In this generality. the answer is no, as proved by W.T. Cowers in 1996. In the present paper, we provide a very simple necessary and sufficient condition on the 10-tuples (k, l, m, n. p, q, r, s, u, v) in N with p+q+u >= 3, r+s+v >= 3, uv >= 1, (p,q)$(0,0), (r,s)not equal(0,0) and u=1 or v=1 or (p. q) = (1, 0) or (r, s) = (0, 1), which guarantees that X is isomorphic to Y whenever these Banach spaces satisfy X(u) similar to X(p)circle plus Y(q), Y(u) similar to X(r)circle plus Y(s), and A(k) circle plus B(l) similar to A(m) circle plus B(n). Namely, delta = +/- 1 or lozenge not equal 0, gcd(lozenge, delta (p + q - u)) divides p + q - u and gcd(lozenge, delta(r + s - v)) divides r + s - v, where 3 = k - I - in + n is the characteristic number of the 4-tuple (k, l, m, n) and lozenge = (p - u)(s - v) - rq is the discriminant of the 6-tuple (p, q, r, s, U, v). We conjecture that this result is in some sense a maximal extension of the classical Pelczynski`s decomposition method in Banach spaces: the case (1, 0. 1, 0, 2. 0, 0, 2. 1. 1). (C) 2009 Elsevier Inc. All rights reserved.

Generalizations of Pelczynski`s decomposition method for Banach spaces containing a complemented copy of their squares

Suppose that X and Y are Banach spaces isomorphic to complemented subspaces of each other. In 1996, W. T. Gowers solved the Schroeder- Bernstein Problem for Banach spaces by showing that X is not necessarily isomorphic to Y. However, if X-2 is complemented in X with supplement A and Y-2 is complemented in Y with supplement B, that is, { X similar to X-2 circle plus A Y similar to Y-2 circle plus B, then the classical Pelczynski`s decomposition method for Banach spaces shows that X is isomorphic to Y whenever we can assume that A = B = {0}. But unfortunately, this is not always possible. In this paper, we show that it is possible to find all finite relations of isomorphism between A and B which guarantee that X is isomorphic to Y. In order to do this, we say that a quadruple (p, q, r, s) in N is a P-Quadruple for Banach spaces if X is isomorphic to Y whenever the supplements A and B satisfy A(p) circle plus B-q similar to A(r) circle plus B-s . Then we prove that (p, q, r, s) is a P-Quadruple for Banach spaces if and only if p - r = s - q = +/- 1.

Experimental Evidence of the Occurrence of Intramolecular Electron Transfer in Catalyzed 1,2-Dioxetane Decomposition

The activation parameters for the thermal decomposition of 13 acridinium-substituted 1,2-dioxetanes, bearing an aromatic moiety, were determined and their chemiluminescence emission quantum yields estimated, utilizing in situ photosensitized 1,2-dioxetane generation and observation of its thermal decomposition kinetics, without isolation of these highly unstable cyclic peroxides. Decomposition rate constants show linear free-energy correlation for electron-withdrawing substituents, with a Hammett reaction constant of rho = 1.3 +/- 0.1, indicating the occurrence of an intramolecular electron transfer from the acridinium moiety to the 1,2-dioxetane ring, as postulated by the intramolecular chemically initiated electron exchange luminescence (CIEEL) mechanism. Emission quantum yield behavior can also be rationalized on the basis of the intramolecular CIEEL mechanism, additionally evidencing its occurrence in this transformation. Both relations constitute the first experimental evidence for the occurrence of the postulated intramolecular electron transfer in the catalyzed and induced decomposition of properly substituted 1,2-dioxetanes.

Thermal analysis of prednicarbate and characterization of thermal decomposition product

In the present work, the thermal behavior of prednicarbate was studied using DSC and TG/DTG. The solid product remaining at the first decomposition step of the drug was isolated by TG, in air and N(2) atmospheres and was characterized using LC-MS/MS, NMR, and IR spectroscopy. It was found that the product at the first thermal decomposition step of prednicarbate corresponds to the elimination of the carbonate group bonding to C(17), and a consequent formation of double bond between C(17) and C(16). Structure elucidation of this degradation product by spectral data has been discussed in detail.

THERMAL BEHAVIOR STUDY AND DECOMPOSITION KINETICS OF SALBUTAMOL UNDER ISOTHERMAL AND NON-ISOTHERMAL CONDITIONS

The thermal decomposition of salbutamol (beta(2) - selective adrenoreceptor) was studied using differential scanning calorimetry (DSC) and thermogravimetry/derivative thermogravimetry (TG/DTG). It was observed that the commercial sample showed a different thermal profile than the standard sample caused by the presence of excipients. These compounds increase the thermal stability of the drug. Moreover, higher activation energy was calculated for the pharmaceutical sample, which was estimated by isothermal and non-isothermal methods for the first stage of the thermal decomposition process. For isothermal experiments the average values were E(act) = 130 kJ mol(-1) (for standard sample) and E(act) = 252 kJ mol(-1) (for pharmaceutical sample) in a dynamic nitrogen atmosphere (50 mL min(-1)). For non-isothermal method, activation energy was obtained from the plot of log heating rates vs. 1/T in dynamic air atmosphere (50 mL min(-1)). The calculated values were E(act) = 134 kJ mol(-1) (for standard sample) and E(act) (=) 139 kJ mol(-1) (for pharmaceutical sample).

Compatibility and decomposition kinetics studies of prednicarbate alone and associated with glyceryl stearate

In this work, TG/DTG and DSC techniques were used to the determination of thermal behavior of prednicarbate alone and associated with glyceryl stearate excipient ( 1: 1 physical mixture). TG/DTG curves obtained for the binary mixture showed a reduction of approximately 37 degrees C to the thermal stability of drug (T(dm/dt-0) (Max)(DTG)). The disappearance of stretching band at 1280 cm(-1) (nu(as) C-O, carbonate group) and the presence of streching band with less intensity at 1750 cm(-1) (nu(s) C-O, ester group) in IR spectrum obtained to the binary mixture submitted at 220 degrees C, when compared with IR spectrum of drug submitted to the same temperature, confirmed the chemical interaction between these substances due to heating. Kinetics parameters of decomposition reaction of prednicarbate were obtained using isothermal (Arrhenius equation) and non-isothermal (Ozawa) methods. The reduction of approximately 45% of activation energy value (E(a)) to the first step of thermal decomposition reaction of drug in the 1:1 (mass/mass) physical mixture was observed by both kinetics methods.

Photocatalytic decomposition of methylene blue via Fenton mechanisms by silicon wafer doped with Au and Cu: a theoretical and experimental study

In this work, we studied the photocatalytic and the structural aspects of silicon wafers doped with Au and Cu submitted to thermal treatment. The materials were obtained by deposition of metals on Si using the sputtering method followed by fast heating method. The photocatalyst materials were characterized by synchrotron-grazing incidence X-ray fluorescence, ultraviolet-visible spectroscopy, X-ray diffraction, and assays of H(2)O(2) degradation. The doping process decreases the optical band gap of materials and the doping with Au causes structural changes. The best photocatalytic activity was found for thermally treated material doped with Au. Theoretical calculations at density functional theory level are in agreement with the experimental data.

Formation and decomposition of N-alkyinaphthalimides: experimental evidences and ab initio description of the reaction pathways

The kinetics of hydrolysis of 1,8-N-butyl-naphthalimide (1,8-NBN) to 1,8-N-butyl-naphthalamide (1,8-NBAmide) and of 2,3-N-butyl-naphthalimide (2,3-NBN) to 2,3-N-butyl-naphthalamide (2,3-NBAmide), as well as the formation of the respective anhydrides from the amides were investigated in a wide acidity range. 1,8-NBN equilibrates with 1,8-NBAmide in mild alkali. Under the same conditions 2,3-NBN quantitatively yields 2,3-NBAmide. Over a wide range of acidities the reactions of the 1,8- and 2,3-N-butyl-naphthalamides (or imides) yield similar products but with widely different rates and at distinct pH`s. Anhydride formation in acid was demonstrated for 1,8-NBAmide. The reactions mechanisms were rationalized in the manifold pathways of ab initio calculations. The differences in rates and pH ranges in the reactions of the 1,8- and 2,3-N-butyl-naphthalamides were attributed to differences in the stability of the tetrahedral intermediates in alkali as well as the relative stabilities of the five and six-membered ring intermediates. The rate of carboxylic acid assisted 1,8-N-Butyl-naphthalamide hydrolysis is one of the largest described for amide hydrolysis models. Copyright (C) 2010 John Wiley & Sons, Ltd.

Solvent assisted decomposition of the tetrahedral intermediate of the transesterification reaction to biodiesel production. A density functional study

B3LYP/6-31 + G(d) calculations were employed to investigate the mechanism of the transesterification reaction between a model monoglyceride and the methoxide and ethoxide anions. The gas-phase results reveal that both reactions have essentially the same activation energy (5.9 kcal mol(-1)) for decomposition of the key tetrahedral intermediate. Solvent effects were included by means of both microsolvation and the polarizable continuum solvation model CPCM. Both solvent approaches reduce the activation energy, however, only the microsolvation model is able to introduce some differentiation between methanol and ethanol, yielding a lower activation energy for decomposition of the tetrahedral intermediate in the reaction with methanol (1.1 kcal mol(-1)) than for the corresponding reaction with ethanol (2.8 kcal mol(-1)), in line with experimental evidences. Analysis of the individual energy components within the CPCM approach reveals that electrostatic interactions are the main contribution to stabilization of the transition state. (C) 2009 Elsevier Ltd. All rights reserved.