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.

An all-substrings common subsequence algorithm

Given two strings A and B of lengths n(a) and n(b), n(a) <= n(b), respectively, the all-substrings longest common subsequence (ALCS) problem obtains, for every substring B` of B, the length of the longest string that is a subsequence of both A and B. The ALCS problem has many applications, such as finding approximate tandem repeats in strings, solving the circular alignment of two strings and finding the alignment of one string with several others that have a common substring. We present an algorithm to prepare the basic data structure for ALCS queries that takes O(n(a)n(b)) time and O(n(a) + n(b)) space. After this preparation, it is possible to build that allows any LCS length to be retrieved in constant time. Some trade-offs between the space required and a matrix of size O(n(b)(2)) the querying time are discussed. To our knowledge, this is the first algorithm in the literature for the ALCS problem. (C) 2007 Elsevier B.V. All rights reserved.

A New Indirect Electroanalytical Method to Monitor the Contamination of Natural Waters with 4-Nitrophenol Using Multiwall Carbon Nanotubes

The electrochemical detection of the hazardous pollutant 4-nitrophenol (4-NP) at low potentials, in order to avoid matrix interferences, is an important research challenge. This study describes the development, electrochemical characterization and utilization of a multiwall carbon nanotube (MWCNT) film electrode for the quantitative determination of 4-NP in natural water. Electrochemical impedence spectroscopy measurements showed that the modified surface exhibits a decrease of ca. 13 times in the charge transfer resistance when compared with a bare glassy carbon (GC) surface. Voltammetric experiments showed the possibility to oxidize a hydroxylamine layer (produced by the electrochemical reduction of 4-NP on the GC/MWNCT surface) in a potential region which is approximately 700 mV less positive than that needed to oxidize 4-NP, thus minimizing the interference of matrix components. The limit of detection for 4-NP obtained using square-wave voltammetry (0.12 mu mol L(-1)) was lower than the value advised by EPA. A natural water sample from a dam located in Sao Carlos (Brazil) was spiked with 4-NP and analyzed by the standard addition method using thee GC/MWCNT electrode, without any further purification step. the recovery procedure yielded a value of 96.5% for such sample, thus confirming the suitability of the developed method to determine 4-NP in natural water samples. The electrochemical determination was compared with that obtained by HPLC with UV-vis detection.