On Finding the Optimal Tree of a Complete Weighted Graph

Seyed Soheil Hosseini, Nick Wormald, Tianhai Tian

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

We want to find a tree where the path length between any two vertices on this tree is as close as possible to their corresponding distance in the complete weighted graph of vertices upon which the tree is built. We use the residual sum of squares as the optimality criterion to formulate this problem, and use the Cholesky decomposition to solve the system of linear equations to optimize weights of a given tree. We also use two metaheuristics, namely Simulated Annealing (SA) and Iterated Local Search (ILS) to optimize the tree structure. Our results suggest that SA and ILS both perform well at finding the optimal tree structure when the dispersion of distances in the complete graph is large. However, when the dispersion of distances is small, only ILS has a solid performance.

Original languageEnglish
Title of host publicationProceedings of the 2020 Federated Conference on Computer Science and Information Systems, FedCSIS 2020
EditorsMaria Ganzha, Leszek Maciaszek, Marcin Paprzycki
Place of PublicationWarsaw Poland
PublisherIEEE, Institute of Electrical and Electronics Engineers
Pages271-275
Number of pages5
Volume21
ISBN (Electronic)9788395541674, 9788395541681
ISBN (Print)9789788395541698
DOIs
Publication statusPublished - Sep 2020
EventFederated Conference on Computer Science and Information Systems, 2020 - Virtual, Sofia, Bulgaria
Duration: 6 Sep 20209 Sep 2020
Conference number: 15th
https://fedcsis.org/2020/

Publication series

NameAnnals of Computer Science and Information Systems
Volume21
ISSN (Print)2300-5963

Conference

ConferenceFederated Conference on Computer Science and Information Systems, 2020
Abbreviated titleFedCSIS 2020
CountryBulgaria
CityVirtual, Sofia
Period6/09/209/09/20
OtherThe mission of the FedCSIS Conference Series is to provide a presentation, discussion and a reputable publication forum in computer science and information systems. The forum invites researchers and practitioners from around the world to contribute their research results focused on their scientific and professional interests in a chosen conference track.
Internet address

Cite this