Search results for "Steiner Tree Problem"

showing 6 items of 16 documents

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…

Protocol Independent MulticastMulticastComputer scienceDistributed computingDistance Vector Multicast Routing ProtocolNetwork topologySteiner tree problemsymbols.namesakeSource-specific multicastDistributed algorithmReliable multicastConvergence (routing)symbolsMulticast transmission Steiner Tree Routing protocolXcastCommunication complexityPragmatic General Multicast
researchProduct

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.

Settore ING-INF/05 - Sistemi Di Elaborazione Delle InformazioniMinimisation (psychology)Mathematical optimizationMulticastHeuristicProcess (computing)STP multicast transmissionNetwork topologySteiner tree problemsymbols.namesakeTree (data structure)symbolsHeuristicsMathematicsITS'98 Proceedings. SBT/IEEE International Telecommunications Symposium (Cat. No.98EX202)
researchProduct

Basic networks: Definition and applications

2009

7 pages, 4 figures, 1 table.-- PMID: 19490867 [PubMed]

Statistics and ProbabilityTheoretical computer scienceInteractomeGeodesicinteractomeSteiner tree problemModels BiologicalGeneral Biochemistry Genetics and Molecular BiologyGraph03 medical and health sciencessymbols.namesakeModuleProtein Interaction MappingmoduleAnimalsSteiner tree030304 developmental biologyMathematicsDiscrete mathematics0303 health sciencesModels StatisticalGeneral Immunology and MicrobiologyApplied Mathematics030302 biochemistry & molecular biologyGeneral MedicinegraphGraphModeling and SimulationsymbolsNeural Networks ComputerGeneral Agricultural and Biological SciencesAlgorithms
researchProduct

Multicast Routing Tree Optimisation

1998

Steiner Tree Problem
researchProduct

Efficient Tree Construction for the Multicast Problem

1999

Steiner Tree Problem Multicast TransmissionSettore ING-INF/05 - Sistemi Di Elaborazione Delle Informazioni
researchProduct

Optimal Resource Discovery Paths of Gnutella2

2008

This paper shows that the performance of peer-to-peer resource discovery algorithms is upper bounded by a k-Steiner minimum tree and proposes an algorithm locating near-optimal query paths for the peer-to-peer resource discovery problem. Global knowledge of the topology and the resources from the peer-to-peer network are required as an input to the algorithm. The algorithm provides an objective measure for defining how good local search algorithms are. The performance is evaluated in simulated peer-to-peer scenarios and in the measured Gnutella2 P2P network topology with four local search algorithms: breadth-first search, self-avoiding random walker, highest degree search and Dynamic Query …

Theoretical computer sciencebusiness.industryComputer scienceNetwork topologyComputer Science::Digital LibrariesSteiner tree problemTree (graph theory)symbols.namesakeRandom walker algorithmSearch algorithmBounded functionsymbolsResource allocationLocal search (optimization)Gnutella2business22nd International Conference on Advanced Information Networking and Applications (aina 2008)
researchProduct