Redirigiendo al acceso original de articulo en 24 segundos...
Inicio  /  Information  /  Vol: 11 Par: 9 (2020)  /  Artículo
ARTÍCULO
TITULO

A Note on Ultrametric Spaces, Minimum Spanning Trees and the Topological Distance Algorithm

Jörg Schäfer    

Resumen

We relate the definition of an ultrametric space to the topological distance algorithm?an algorithm defined in the context of peer-to-peer network applications. Although (greedy) algorithms for constructing minimum spanning trees such as Prim?s or Kruskal?s algorithm have been known for a long time, they require the complete graph to be specified and the weights of all edges to be known upfront in order to construct a minimum spanning tree. However, if the weights of the underlying graph stem from an ultrametric, the minimum spanning tree can be constructed incrementally and it is not necessary to know the full graph in advance. This is possible, because the join algorithm responsible for joining new nodes on behalf of the topological distance algorithm is independent of the order in which the nodes are added due to the property of an ultrametric. Apart from the mathematical elegance which some readers might find interesting in itself, this provides not only proofs (and clearer ones in the opinion of the author) for optimality theorems (i.e., proof of the minimum spanning tree construction) but a simple proof for the optimality of the reconstruction algorithm omitted in previous publications too. Furthermore, we define a new algorithm by extending the join algorithm to minimize the topological distance and (network) latency together and provide a correctness proof.

 Artículos similares

       
 
Chuanzhe Gao, Shidang Li, Mingsheng Wei, Siyi Duan and Jinsong Xu    
With the rapid development of wireless communication networks and Internet of Things technology (IoT), higher requirements have been put forward for spectrum resource utilization and system performance. In order to further improve the utilization of spec... ver más
Revista: Information

 
Giorgio Lazzarinetti, Riccardo Dondi, Sara Manzoni and Italo Zoppis    
Solving combinatorial problems on complex networks represents a primary issue which, on a large scale, requires the use of heuristics and approximate algorithms. Recently, neural methods have been proposed in this context to find feasible solutions for r... ver más
Revista: Algorithms

 
Chunchang Zhang and Ji Zeng    
The real-time transmission of ship status data from vessels to shore is crucial for live status monitoring and guidance. Traditional reliance on expensive maritime satellite systems for this purpose is being reconsidered with the emergence of the global ... ver más

 
Fangling Leng, Fan Li, Yubin Bao, Tiancheng Zhang and Ge Yu    
As graph models become increasingly prevalent in the processing of scientific data, the exploration of effective methods for the mining of meaningful patterns from large-scale graphs has garnered significant research attention. This paper delves into the... ver más
Revista: Applied Sciences

 
Pir Dino Soomro, Xianping Fu, Muhammad Aslam, Dani Elias Mfungo and Arsalan Ali    
An imperative application of artificial intelligence (AI) techniques is visual object detection, and the methods of visual object detection available currently need highly equipped datasets preserved in a centralized unit. This usually results in high tr... ver más
Revista: Applied Sciences