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.

Small-Sample Corrections for Score Tests in Birnbaum-Saunders Regressions

In this article, we deal with the issue of performing accurate small-sample inference in the Birnbaum-Saunders regression model, which can be useful for modeling lifetime or reliability data. We derive a Bartlett-type correction for the score test and numerically compare the corrected test with the usual score test and some other competitors.

Improved likelihood inference in Birnbaum-Saunders regressions

The Birnbaum-Saunders regression model is commonly used in reliability studies. We address the issue of performing inference in this class of models when the number of observations is small. Our simulation results suggest that the likelihood ratio test tends to be liberal when the sample size is small. We obtain a correction factor which reduces the size distortion of the test. Also, we consider a parametric bootstrap scheme to obtain improved critical values and improved p-values for the likelihood ratio test. The numerical results show that the modified tests are more reliable in finite samples than the usual likelihood ratio test. We also present an empirical application. (C) 2009 Elsevier B.V. All rights reserved.

Short-time behaviour of demand and price viewed through an exactly solvable model for heterogeneous interacting market agents

We introduce a stochastic heterogeneous interacting-agent model for the short-time non-equilibrium evolution of excess demand and price in a stylized asset market. We consider a combination of social interaction within peer groups and individually heterogeneous fundamentalist trading decisions which take into account the market price and the perceived fundamental value of the asset. The resulting excess demand is coupled to the market price. Rigorous analysis reveals that this feedback may lead to price oscillations, a single bounce, or monotonic price behaviour. The model is a rare example of an analytically tractable interacting-agent model which allows LIS to deduce in detail the origin of these different collective patterns. For a natural choice of initial distribution, the results are independent of the graph structure that models the peer network of agents whose decisions influence each other. (C) 2009 Elsevier B.V. All rights reserved.

Discontinuous Galerkin approximation of two-phase flows in heterogeneous porous media with discontinuous capillary pressures

We design and investigate a sequential discontinuous Galerkin method to approximate two-phase immiscible incompressible flows in heterogeneous porous media with discontinuous capillary pressures. The nonlinear interface conditions are enforced weakly through an adequate design of the penalties on interelement jumps of the pressure and the saturation. An accurate reconstruction of the total velocity is considered in the Raviart-Thomas(-Nedelec) finite element spaces, together with diffusivity-dependent weighted averages to cope with degeneracies in the saturation equation and with media heterogeneities. The proposed method is assessed on one-dimensional test cases exhibiting rough solutions, degeneracies, and capillary barriers. Stable and accurate solutions are obtained without limiters. (C) 2010 Elsevier B.V. All rights reserved.

Reactions of toluquinone - cyclopentadiene Diels -Alder epoxide adducts with nucleophiles under heterogeneous conditions

Toluquinone-cyclopentadiene Diels-Alder epoxide adducts react with sulfur and oxygen nucleophiles under heterogeneous conditions, leading to products resulting from the epoxide ring opening and from skeletal rearrangement, respectively. Pyrolysis of the sulfanyl adducts gave the new 3-sulfanyltoluquinones (1).

Heterogeneous photocatalytic degradation of acid dyes in aqueous TiO2 suspensions: Kinetics and toxicity

This work assesses the photocatalytic (TiO2/UV) degradation of a simulated acid dye bath (Yellow 3, Red 51, Blue 74, and auxiliary chemicals). Color and phytotoxicity removal were monitored by spectrophotometry and lettuce (Lactuca sativa) seeds as the test organism, respectively. Mineralization was determined by DOC analyses. Photocatalytic, photolytic, and adsorption experiments were performed, showing that adsorption was negligible. After 240 minutes of irradiation, it was achieved 96% and 78% of color removal with photocatalysis and photolysis, respectively. 37% of mineralization occurred with photocatalysis only. The dye bath was rendered completely non-toxic after 60 minutes of photocatalytic treatment; the same result was only achieved with photolysis after 90 minutes. A kinetic model composed of two first-order in series reactions was used. The first photocatalytic decolorization rate constant was k(1) = 0.062 min(-1) and the second k(2) = 0.0043 min(-1), approximately two times greater than the photolytic ones.

Heterogeneous photocatalytic degradation of reactive dyes in aqueous TiO(2) suspensions: Decolorization kinetics

This work assesses the photocatalytic (TiO(2)/UV) degradation of a simulated reactive dye bath (Black 5, Red 239, Yellow 17, and auxiliary chemicals). Color removal was monitored by spectrophotometry. Mineralization was determined by DOC analyses. Photocatalytic, photolytic, and adsorption experiments were performed, showing that adsorption was negligible. After 30 min of irradiation, it was achieved 97% and 40% of color removal with photocatalysis and photolysis, respectively. No mineralization occurred within 30 min. A kinetic model composed of two, first-order in-series reactions was used. The first photocatalytic decolorization rate constant was k(1) = 2.6 min(-1) and the second k(2) = 0.011 min(-1). The fast decolorization of Reactive Black 5 dye is an indication that the number of azo and vinylsulfone groups in the dye molecule maybe a determining factor for the increased photolytic and photocatalytic color removal and degradation rates. (C) 2008 Elsevier B.V. All rights reserved.