Search results for "Steiner"
showing 10 items of 47 documents
A Grid Enabled Parallel Hybrid Genetic Algorithm for SPN
2004
This paper presents a combination of a parallel Genetic Algorithm (GA) and a local search methodology for the Steiner Problem in Networks (SPN). Several previous papers have proposed the adoption of GAs and others metaheuristics to solve the SPN demonstrating the validity of their approaches. This work differs from them for two main reasons: the dimension and the features of the networks adopted in the experiments and the aim from which it has been originated. The reason that aimed this work was namely to assess deterministic and computationally inexpensive algorithms which can be used in practical engineering applications, such as the multicast transmission in the Internet. The large dimen…
New Algorithms for Computing Phylogenetic Biodiversity
2014
A common problem that appears in many case studies in ecology is the following: given a rooted phylogenetic tree \(\mathcal{T}\) and a subset R of its leaf nodes, we want to compute the distance between the elements in R. A very popular distance measure that can be used for this reason is the Phylogenetic Diversity (PD), which is defined as the cost of the minimum weight Steiner tree in \(\mathcal{T}\) that spans the nodes in R. To analyse the value of the PD for a given set R it is important also to calculate the variance of this measure. However, the best algorithm known so far for computing the variance of the PD is inefficient; for any input tree \(\mathcal{T}\) that consists of n nodes…
Recent mathematical approaches to reconstruct phylogenies: A chemosystematist's and botanist's view
1989
Some basic problems of mathematical phylogenetics are discussed. While algorithms regularly depend on the principle of parsimony, some features of phylogenesis interfere with that principle. Nonrandomness of the distribution of mutations as well as the inconstancy of the molecular clock in time and within a given sequence can bias the calculated relationships of closely related taxa. True comparability of sequences is difficult to establish, since this requires defining of homology of positions and of functions of amino acids as well. Parallelism and convergence can give rise to errors in establishing homology. Furthermore, they are difficult to be integrated into a consistent mathematical …
A Dynamic Distributed Algorithm for Multicast Path Setup
2005
In the past few years, there has been a considerable work on multicast route selection techniques, with the aim to design scalable protocols which can guarantee an efficient use of network resources. Steiner tree-based multicast algorithms produce optimal trees, but they are prohibitively expensive. For this reason, heuristic methods are generally employed. Conventional centralized Steiner heuristics provide effective solutions, but they are unpractical for large networks, since they require a complete knowledge of the network topology. In this paper, we propose a new distributed approach that is efficient and suitable for real network adoption. Performance evaluation indicates that it outp…
An efficient distributed approach for dynamic multicast trees
2005
In this paper we present a distributed algorithm for constructing efficient multicast trees in large networks. The algorithm allows the set up of effective distribution trees using a coordination protocol among the network nodes. The algorithm has been implemented and extensively tested both in simulation, and on experimental networks. Performance evaluation indicates that our approach outperforms the state-of-the-art distributed algorithms for multicast tree setup, providing good levels of convergence time and communication complexity. Furthermore, we introduce a distributed technique for dynamically updating the multicast tree. The approach monitors the accumulated damage as nodes join or…
Impiego dei nematodi entomopatogeni in ambiente urbano per il controllo del Punteruolo rosso
2009
Effects of Steinernema carpocapsae (Nematoda: Steinernematidae) on biological parameters of larvae responses of Rhynchophorus ferrugineus (Coleoptera…
2013
Rhynchophorus ferrugineus (Coleoptera: Curculionidae) known as the Red Palm Weevil (RPW) is becoming more and more of a problem in Italy, and especially in Sicily, where it is well adapted. The infestations are mainly in the urban areas, and for that reason, chemical control is not advisable. Data from literature show that entomopathogenic nematodes (EPN) particularly Steirnenema carpocapsae, have a quite successfully control of RPW. However, results coming from the laboratories are often in contrast with each other and no data are available on precise doses and S. carpocapsae seems not be able to reproduce itself in the host. The effect of EPN on the RPW immune system is totally unknown. D…
Efficient tree construction for the multicast problem
2002
A new heuristic for the Steiner minimal tree problem is presented. The method described is based on the detection of particular sets of nodes in networks, the "hot spot" sets, which are used to obtain better approximations of the optimal solutions. An algorithm is also proposed which is capable of improving the solutions obtained by classical heuristics, by means of a stirring process of the nodes in solution trees. Classical heuristics and an enumerative method are used as comparison terms in the experimental analysis which demonstrates the capability of the heuristic discussed.
Basic networks: Definition and applications
2009
7 pages, 4 figures, 1 table.-- PMID: 19490867 [PubMed]