Efficient Forest Data Structure for Evolutionary Algorithms Applied to Network Design

The design of a network is a solution to several engineering and science problems. Several network design problems are known to be NP-hard, and population-based metaheuristics like evolutionary algorithms (EAs) have been largely investigated for such problems. Such optimization methods simultaneously generate a large number of potential solutions to investigate the search space in breadth and, consequently, to avoid local optima. Obtaining a potential solution usually involves the construction and maintenance of several spanning trees, or more generally, spanning forests. To efficiently explore the search space, special data structures have been developed to provide operations that manipulate a set of spanning trees (population). For a tree with n nodes, the most efficient data structures available in the literature require time O(n) to generate a new spanning tree that modifies an existing one and to store the new solution. We propose a new data structure, called node-depth-degree representation (NDDR), and we demonstrate that using this encoding, generating a new spanning forest requires average time O(root n). Experiments with an EA based on NDDR applied to large-scale instances of the degree-constrained minimum spanning tree problem have shown that the implementation adds small constants and lower order terms to the theoretical bound.

Removal of Pb2+ from aqueous solutions using two Brazilian rocks containing zeolites

The removal of Pb2+ from aqueous solution by two Brazilian rocks that contain zeolites-amygdaloidal dacite (ZD) and sandstone (ZS)-was examined by batch experiments. ZD contains mordenite and ZS, stilbite. The effects of contact time, concentration of metal in solution and capacity of Na+ to recover the adsorbed metals were evaluated at room temperature (20A degrees C). The sorption equilibrium was reached in the 30 min of agitation time. Both materials removed 100% of Pb2+ from solutions at concentrations up to 50 mg/L, and at concentrations larger than 100 mg/L of Pb2+, the adsorption capacity of sandstone was more efficient than that of amygdaloidal dacite due to the larger quantities and the type of zeolites (stilbite) in the cement of this rock. All adsorbed Pb2+ was easily replaced by Na+ in both samples. The analysis of the adsorption models using nonlinear regression revealed that the Sips and the Freundlich isotherms provided the best fit for the ZS and ZD experimental data, respectively, indicating the heterogeneous adsorption surfaces of these zeolites.

Cryptanalysis of an efficient three-party password-based key exchange scheme

Three-party password-authenticated key exchange (3PAKE) protocols allow entities to negotiate a secret session key with the aid of a trusted server with whom they share a human-memorable password. Recently, Lou and Huang proposed a simple 3PAKE protocol based on elliptic curve cryptography, which is claimed to be secure and to provide superior efficiency when compared with similar-purpose solutions. In this paper, however, we show that the solution is vulnerable to key-compromise impersonation and offline password guessing attacks from system insiders or outsiders, which indicates that the empirical approach used to evaluate the scheme's security is flawed. These results highlight the need of employing provable security approaches when designing and analyzing PAKE schemes. Copyright (c) 2011 John Wiley & Sons, Ltd.