Two ex situ fungal technologies to treat contaminated soil

Wood-degrading fungi are able to degrade a large range of recalcitrant pollutants which resemble the lignin biopolymer. This ability is attributed to the production of lignin-modifying enzymes, which are extracellular and non-specific. Despite the potential of fungi in bioremediation, there is still an understanding gap in terms of the technology. In this thesis, the feasibility of two ex situ fungal bioremediation methods to treat contaminated soil was evaluated. Treatment of polycyclic aromatic hydrocarbons (PAHs)-contaminated marsh soil was studied in a stirred slurry-phase reactor. Due to the salt content in marsh soil, fungi were screened for their halotolerance, and the white-rot fungi Lentinus tigrinus, Irpex lacteus and Bjerkandera adusta were selected for further studies. These fungi degraded 40 - 60% of a PAH mixture (phenanthrene, fluoranthene, pyrene and chrysene) in a slurry-phase reactor (100 ml) during 30 days of incubation. Thereafter, B. adusta was selected to scale-up and optimize the process in a 5 L reactor. Maximum degradation of dibenzothiophene (93%), fluoranthene (82%), pyrene (81%) and chrysene (83%) was achieved with the free mycelium inoculum of the highest initial biomass (2.2 g/l). In autoclaved soil, MnP was the most important enzyme involved in PAH degradation. In non-sterile soil, endogenous soil microbes together with B. adusta also degraded the PAHs extensively, suggesting a synergic action between soil microbes and the fungus. A fungal solid-phase cultivation method to pretreat contaminated sawmill soil with high organic matter content was developed to enhance the effectiveness of the subsequent soil combustion. In a preliminary screening of 146 fungal strains, 28 out of 52 fungi, which extensively colonized non-sterile contaminated soil, were litter-decomposing fungi. The 18 strains further selected were characterized by their production of lignin-modifying and hydrolytic enzymes, of which MnP and endo-1,4-β-glucanase were the main enzymes during cultivation on Scots pine (Pinus sylvestris) bark. Of the six fungi selected for further tests, Gymnopilus luteofolius, Phanerochaete velutina, and Stropharia rugosoannulata were the most active soil organic matter degraders. The results showed that a six-month pretreatment of sawmill soil would result in a 3.5 - 9.5% loss of organic matter, depending on the fungus applied. The pretreatment process was scaled-up for a 0.56 m3 reactor, in which perforated plastic tubes filled with S. rugosoannulata growing on pine bark were introduced into the soil. The fungal pretreatment resulted in a soil mass loss of 30.5 kg, which represents 10% of the original soil mass (308 kg). Despite the fact that Scots pine bark contains several antimicrobial compounds, it was a suitable substrate for fungal growth and promoter of the production of oxidative enzymes, as well as an excellent and cheap natural carrier of fungal mycelium. This thesis successfully developed two novel fungal ex situ bioremediation technologies and introduce new insights for their further full-scale application. Ex situ slurry-phase fungal reactors might be applied in cases when the soil has a high water content or when the contaminant bioavailability is low; for example, in wastewater treatment plants to remove pharmaceutical residues. Fungal solid-phase bioremediation is a promising remediation technology to ex situ or in situ treat contaminated soil.

Almost Stable Matchings by Truncating the Gale–Shapley Algorithm

We show that the ratio of matched individuals to blocking pairs grows linearly with the number of propose–accept rounds executed by the Gale–Shapley algorithm for the stable marriage problem. Consequently, the participants can arrive at an almost stable matching even without full information about the problem instance; for each participant, knowing only its local neighbourhood is enough. In distributed-systems parlance, this means that if each person has only a constant number of acceptable partners, an almost stable matching emerges after a constant number of synchronous communication rounds. We apply our results to give a distributed (2 + ε)-approximation algorithm for maximum-weight matching in bicoloured graphs and a centralised randomised constant-time approximation scheme for estimating the size of a stable matching.

A local 2-approximation algorithm for the vertex cover problem

We present a distributed 2-approximation algorithm for the minimum vertex cover problem. The algorithm is deterministic, and it runs in (Δ + 1)2 synchronous communication rounds, where Δ is the maximum degree of the graph. For Δ = 3, we give a 2-approximation algorithm also for the weighted version of the problem.

A simple local 3-approximation algorithm for vertex cover

We present a local algorithm (constant-time distributed algorithm) for finding a 3-approximate vertex cover in bounded-degree graphs. The algorithm is deterministic, and no auxiliary information besides port numbering is required. (c) 2009 Elsevier B.V. All rights reserved.

A local 2-approximation algorithm for the vertex cover problem

We present a distributed 2-approximation algorithm for the minimum vertex cover problem. The algorithm is deterministic, and it runs in (Δ + 1)2 synchronous communication rounds, where Δ is the maximum degree of the graph. For Δ = 3, we give a 2-approximation algorithm also for the weighted version of the problem.

Analysing local algorithms in location-aware quasi-unit-disk graphs

A local algorithm with local horizon r is a distributed algorithm that runs in r synchronous communication rounds; here r is a constant that does not depend on the size of the network. As a consequence, the output of a node in a local algorithm only depends on the input within r hops from the node. We give tight bounds on the local horizon for a class of local algorithms for combinatorial problems on unit-disk graphs (UDGs). Most of our bounds are due to a refined analysis of existing approaches, while others are obtained by suggesting new algorithms. The algorithms we consider are based on network decompositions guided by a rectangular tiling of the plane. The algorithms are applied to matching, independent set, graph colouring, vertex cover, and dominating set. We also study local algorithms on quasi-UDGs, which are a popular generalisation of UDGs, aimed at more realistic modelling of communication between the network nodes. Analysing the local algorithms on quasi-UDGs allows one to assume that the nodes know their coordinates only approximately, up to an additive error. Despite the localisation error, the quality of the solution to problems on quasi-UDGs remains the same as for the case of UDGs with perfect location awareness. We analyse the increase in the local horizon that comes along with moving from UDGs to quasi-UDGs.