{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T13:16:45Z","timestamp":1774876605488,"version":"3.50.1"},"reference-count":9,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2020,8,28]],"date-time":"2020-08-28T00:00:00Z","timestamp":1598572800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"German Federal 223 Ministry for Economic Affairs and Energy","award":["Central Innovation Programme SMEs (ZIM)"],"award-info":[{"award-number":["Central Innovation Programme SMEs (ZIM)"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information"],"abstract":"<jats:p>We relate the definition of an ultrametric space to the topological distance algorithm\u2014an algorithm defined in the context of peer-to-peer network applications. Although (greedy) algorithms for constructing minimum spanning trees such as Prim\u2019s or Kruskal\u2019s 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.<\/jats:p>","DOI":"10.3390\/info11090418","type":"journal-article","created":{"date-parts":[[2020,8,28]],"date-time":"2020-08-28T09:17:08Z","timestamp":1598606228000},"page":"418","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A Note on Ultrametric Spaces, Minimum Spanning Trees and the Topological Distance Algorithm"],"prefix":"10.3390","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4797-0306","authenticated-orcid":false,"given":"J\u00f6rg","family":"Sch\u00e4fer","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, Frankfurt University of Applied Sciences, Nibelungenplatz 1, D-60318 Frankfurt am Main, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,8,28]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Alekseev, S., and Sch\u00e4fer, J. (2016, January 2\u20133). A New Algorithm for Construction of a P2P Multicast Hybrid Overlay Tree Based on Topological Distances. Proceedings of the Seventh International Conference on Networks & Communications, Z\u00fcrich, Switzerland.","DOI":"10.5121\/csit.2016.60126"},{"key":"ref_2","first-page":"1","article-title":"Evaluation of a Topological Distance Algorithm for Construction of a P2P Multicast Hybrid Overlay Tree","volume":"8","author":"Alekseev","year":"2016","journal-title":"Int. J. Comput. Netw. Commun."},{"key":"ref_3","first-page":"433","article-title":"Nombres semi-r\u00e9els et espaces ultram\u00e9triques","volume":"219","author":"Krasner","year":"1944","journal-title":"C. R. Acad. Sci."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Korte, B., Lovasz, L., and Schrader, R. (1991). Greedoids, Springer.","DOI":"10.1007\/978-3-642-58191-5"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/BF02579192","article-title":"Structural properties of greedoids","volume":"3","author":"Korte","year":"1983","journal-title":"Combinatorica"},{"key":"ref_6","unstructured":"Pulleyblank, W.R. (1984). Greedoids\u2014A Structural Framework for the Greedy Algorithm. Progress in Combinatorial Optimization, Academic Press."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Silva, M.A., Bertone, R., and Sch\u00e4fer, J. (2019, January 1\u20133). Topology Distribution for Video-Conferencing Applications. Proceedings of the 2019 10th International Conference on Networks of the Future (NoF), Rome, Italy.","DOI":"10.1109\/NoF47743.2019.9014957"},{"key":"ref_8","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2009). Introduction to Algorithms, MIT Press. [3rd ed.]."},{"key":"ref_9","unstructured":"Szeszl\u00e9r, D. (2019, January 27\u201330). Optimality of the Greedy Algorithm in Greedoids. Proceedings of the 11th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, Tokyo, Japan."}],"container-title":["Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2078-2489\/11\/9\/418\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:04:22Z","timestamp":1760177062000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2078-2489\/11\/9\/418"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,28]]},"references-count":9,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2020,9]]}},"alternative-id":["info11090418"],"URL":"https:\/\/doi.org\/10.3390\/info11090418","relation":{},"ISSN":["2078-2489"],"issn-type":[{"value":"2078-2489","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,28]]}}}