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.

FT-Raman, FTIR and density functional theory studies of a hydrogen-bonded formamide: pyridine complex

Raman and IR experiments have been carried out on formamide (FA) and pyridine (Py) mixtures at different compositions. The appearance of a new Raman band at 996 cm(-1) (nu(1) region of Py), whose intensity depends on the FA concentration, is assigned to an FA: Py adduct and this result is in excellent agreement with those of other authors who employed noisy light-based coherent Raman scattering spectroscopy (I((2)) CARS). Another band at 1587 cm(-1) (nu(8) region of Py) has been observed for the first time by using Raman and IR spectroscopies. Its intensity shows the same dependence on the FA concentration and this fact allows us to also attribute it to an FA: Py adduct. The good relationship between the Raman and IR data demonstrates the potential of the vibrational spectroscopy for this kind of study. Owing to higher absolute Raman scattering cross section, the nu(1) region of Py has been chosen for the quantitative analysis and a stoichiometry of 1 : 1 FA: Py is reported. The experimental data are very well supported by the density functional theory (OFT) calculation, which was employed for the first time to the present system. Furthermore, the actual investigation shows an excellent agreement with those reported from computational calculations for similar systems. A comparison with our previous studies confirms that: the solvent dielectric constant determines the stoichiometry of a given Lewis acid-base adduct in the infinite dilution limit. Copyright (C) 2009 John Wiley & Sons, Ltd.