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.

In-depth search focused on furans, lactones, volatile phenols, and acetals as potential age markers of Madeira wines by comprehensive two-dimensional gas chromatography with time-of-flight mass spectrometry combined with solid phase microextraction

The establishment of potential age markers of Madeira wine is of paramount significance as it may contribute to detect frauds and to ensure the authenticity of wine. Considering the chemical groups of furans, lactones, volatile phenols, and acetals, 103 volatile compounds were tentatively identified; among these, 71 have been reported for the first time in Madeira wines. The chemical groups that could be used as potential age markers were predominantly acetals, namely, diethoxymethane, 1,1-diethoxyethane, 1,1-diethoxy-2-methyl-propane, 1-(1-ethoxyethoxy)-pentane, trans-dioxane and 2-propyl-1,3-dioxolane, and from the other chemical groups, 5-methylfurfural and cis-oak-lactone, independently of the variety and the type of wine. GC × GC-ToFMS system offers a more useful approach to identify these compounds compared to previous studies using GC−qMS, due to the orthogonal systems, that reduce coelution, increase peak capacity and mass selectivity, contributing to the establishment of new potential Madeira wine age markers. Remarkable results were also obtained in terms of compound identification based on the organized structure of the peaks of structurally related compounds in the GC × GC peak apex plots. This information represents a valuable approach for future studies, as the ordered-structure principle can considerably help the establishment of the composition of samples. This new approach provides data that can be extended to determine age markers of other types of wines.