Search results for: S. J. Gismondi

Authors: E. R. Swart, S. J. Gismondi, N. R. Swart, C. E. Bell

Abstract:

We present an heuristic algorithm that decides graph non-Hamiltonicity. All graphs are directed, each undirected edge regarded as a pair of counter directed arcs. Each of the n! Hamilton cycles in a complete graph on n+1 vertices is mapped to an n-permutation matrix P where p(u,i)=1 if and only if the ith arc in a cycle enters vertex u, starting and ending at vertex n+1. We first create exclusion set E by noting all arcs (u, v) not in G, sufficient to code precisely all cycles excluded from G i.e. cycles not in G use at least one arc not in G. Members are pairs of components of P, {p(u,i),p(v,i+1)}, i=1, n-1. A doubly stochastic-like relaxed LP formulation of the Hamilton cycle decision problem is constructed. Each {p(u,i),p(v,i+1)} in E is coded as variable q(u,i,v,i+1)=0 i.e. shrinks the feasible region. We then implement the Weak Closure Algorithm (WCA) that tests necessary conditions of a matching, together with Boolean closure to decide 0/1 variable assignments. Each {p(u,i),p(v,j)} not in E is tested for membership in E, and if possible, added to E (q(u,i,v,j)=0) to iteratively maximize |E|. If the WCA constructs E to be maximal, the set of all {p(u,i),p(v,j)}, then G is decided non-Hamiltonian. Only non-Hamiltonian G share this maximal property. Ten non-Hamiltonian graphs (10 through 104 vertices) and 2000 randomized 31 vertex non-Hamiltonian graphs are tested and correctly decided non-Hamiltonian. For Hamiltonian G, the complement of E covers a matching, perhaps useful in searching for cycles. We also present an example where the WCA fails.

Keywords: Hamilton cycle decision problem, computational complexity theory, graph theory, theoretical computer science

Procedia PDF Downloads 374

Authors: Eric Gismondi, Aurelie Bigot-Clivot

Abstract:

Endocrine disruptors (EDCs) are well known to disrupt the development and the reproduction of exposed organisms. Although this point has been studied in vertebrate models, the limited knowledge of the endocrine system of invertebrates makes the evaluation of EDCs effects difficult. However, invertebrates represent the major part of aquatic ecosystems, such as amphipods Gammaridea, which are crucial for their functioning (e.g., litter degradation, food resource). Moreover, gammarids are hosts of parasites such as vertically-transmitted microsporidia (microsporidia VT), which could be confounding factors in assessment of EDC effects. Indeed, some microsporidia VT could have endocrine effects by their own present in the host since it was observed for example, a feminization of juvenile males, which become phenotypic females. This work evaluated the impact of ethinylestradiol (EE₂, estrogenic), cyproterone acetate (CPA, anti-androgenic), 4-hydroxytamoxifen (4HT, anti-estrogenic) and 17α-methyltestosterone (17MT - androgenic), on the 20-hydroxyecdysone concentration (i.e. 20HE - molt process) and the vitellogenin gene expression (i.e. reproduction) in the freshwater amphipod Gammarus pulex, after a 96h laboratory exposure. In addition, the presence of microsporidia VT was verified in order to analyze the effect of this confounding factor. Results of this study shown that, although endocrine systems of invertebrates and vertebrates are different, EDCs proved in vertebrates could also affect biological functions hormonally controlled in invertebrates. Indeed, the molt process of crustaceans was disrupted in the first stage (i.e. 20-HE concentration) and therefore, could affect, at the long term, the population dynamic. In addition, it was observed that G. pulex was differently impacted according to the gender and parasitism, which underline the importance to take into account these confounding factors to better evaluate the EDCs impact on invertebrate populations.

Keywords: endocrine disruption, gammarus sp., molt, parasitism

Procedia PDF Downloads 166