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.

Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width

Let M = (V, E, A) be a mixed graph with vertex set V, edge set E and arc set A. A cycle cover of M is a family C = {C(1), ... , C(k)} of cycles of M such that each edge/arc of M belongs to at least one cycle in C. The weight of C is Sigma(k)(i=1) vertical bar C(i)vertical bar. The minimum cycle cover problem is the following: given a strongly connected mixed graph M without bridges, find a cycle cover of M with weight as small as possible. The Chinese postman problem is: given a strongly connected mixed graph M, find a minimum length closed walk using all edges and arcs of M. These problems are NP-hard. We show that they can be solved in polynomial time if M has bounded tree-width. (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.

Asymmetric Ramsey Properties of Random Graphs Involving Cliques

Consider the following problem: Forgiven graphs G and F(1),..., F(k), find a coloring of the edges of G with k colors such that G does not contain F; in color i. Rodl and Rucinski studied this problem for the random graph G,,, in the symmetric case when k is fixed and F(1) = ... = F(k) = F. They proved that such a coloring exists asymptotically almost surely (a.a.s.) provided that p <= bn(-beta) for some constants b = b(F,k) and beta = beta(F). This result is essentially best possible because for p >= Bn(-beta), where B = B(F, k) is a large constant, such an edge-coloring does not exist. Kohayakawa and Kreuter conjectured a threshold function n(-beta(F1,..., Fk)) for arbitrary F(1), ..., F(k). In this article we address the case when F(1),..., F(k) are cliques of different sizes and propose an algorithm that a.a.s. finds a valid k-edge-coloring of G(n,p) with p <= bn(-beta) for some constant b = b(F(1),..., F(k)), where beta = beta(F(1),..., F(k)) as conjectured. With a few exceptions, this algorithm also works in the general symmetric case. We also show that there exists a constant B = B(F,,..., Fk) such that for p >= Bn(-beta) the random graph G(n,p) a.a.s. does not have a valid k-edge-coloring provided the so-called KLR-conjecture holds. (C) 2008 Wiley Periodicals, Inc. Random Struct. Alg., 34, 419-453, 2009

Reliable and fast sensor for in vitro evaluation of solar protection factor based on the photobleaching kinetics of a nanocrystalline TiO(2)/dye UV-dosimeter

A reliable and fast sensor for in vitro evaluation of solar protection factors (SPFs) of cosmetic products, based on the photobleaching kinetics of a nanocrystalline TiO(2)/dye UV-dosimeter, has been devised. The accuracy, robustness and suitability of the new device was demonstrated by the excellent matching of the predicted and the in vivo results up to SPF 70, for four standard samples analyzed in blind. These results strongly suggest that our device can be useful for routine SPF evaluation in laboratories devoted to the development or production of cosmetic formulations, since the conventional in vitro methods tend to exhibit unacceptably high errors above SPF similar to 30 and the conventional in vivo methods tend to be expensive and exceedingly time consuming. (C) 2011 Elsevier B.V. All rights reserved.

Evaluation of a carbon paste electrode modified with organofunctionalised SBA-15 nanostructured silica in the simultaneous determination of divalent lead, copper and mercury ions

The performance of a carbon paste electrode (CPE) modified with SBA-15 nanostructured silica organofunctionalised with 2-benzothiazolethiol in the simultaneous determination of Pb(II), Cu(II) and Hg(II) ions in natural water and sugar cane spirit (cachaca) is described. Pb(II), Cu(II) and Hg(II) were pre-concentrated on the surface of the modified electrode by complexing with 2-benzothiazolethiol and reduced at a negative potential (-0.80 V). Then the reduced products were oxidised by DPASV procedure. The fact that three stripping peaks appeared on the voltammograms at the potentials of -0.48 V (Pb2+), -0.03 V (Cu2+) and +0.36 V (Hg2+) in relation to the SCE, demonstrates the possibility of simultaneous determination of Pb2+, Cu2+ and Hg2+. The best results were obtained under the following optimised conditions: 100 mV pulse amplitude, 3 min accumulation time, 25 mV s(-1) scan rate in phosphate solution pH 3.0. Using such parameters, calibration graphs were linear in the concentration ranges of 3.00-70.0 x 10(-7) mol L-1 (Pb2+), 8.00-100.0 X 10(-7) mol L-1 (Cu2+) and 2.00-10.0 x 10(-6) mol L-1 (Hg2+). Detection limits of 4.0 x 10(-8) mol L-1 (Pb2+), 2.0 x 10(-7) mol L-1 (Cu2+) and 4.0 x 10(-7) mol L-1 (Hg2+) were obtained at the signal noise ratio (SNR) of 3. The results indicate that this electrode is sensitive and effective for simultaneous determination of Pb2+, Cu2+ and Hg2+ in the analysed samples. (C) 2008 Published by Elsevier B.V.