On Finding the Optimal Tree of a Complete Weighted Graph

Seyed Soheil Hosseini; Nick Wormald; Tianhai Tian

doi:10.15439/2020F4

On Finding the Optimal Tree of a Complete Weighted Graph

Seyed Soheil Hosseini, Nick Wormald, Tianhai Tian

School of Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-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 language	English
Title of host publication	Proceedings of the 2020 Federated Conference on Computer Science and Information Systems, FedCSIS 2020
Editors	Maria Ganzha, Leszek Maciaszek, Marcin Paprzycki
Place of Publication	Warsaw Poland
Publisher	IEEE, Institute of Electrical and Electronics Engineers
Pages	271-275
Number of pages	5
Volume	21
ISBN (Electronic)	9788395541674, 9788395541681
DOIs	https://doi.org/10.15439/2020F4
Publication status	Published - Sept 2020
Event	Federated Conference on Computer Science and Information Systems (FedCSIS) 2020 - Virtual, Sofia, Bulgaria Duration: 6 Sept 2020 → 9 Sept 2020 Conference number: 15th https://fedcsis.org/2020/ https://ieeexplore.ieee.org/xpl/conhome/9217610/proceeding (Proceedings)

Publication series

Name	Annals of Computer Science and Information Systems
Volume	21
ISSN (Print)	2300-5963

Conference

Conference	Federated Conference on Computer Science and Information Systems (FedCSIS) 2020
Abbreviated title	FedCSIS 2020
Country/Territory	Bulgaria
City	Virtual, Sofia
Period	6/09/20 → 9/09/20
Other	The 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	https://fedcsis.org/2020/ https://ieeexplore.ieee.org/xpl/conhome/9217610/proceeding (Proceedings)

Access to Document

10.15439/2020F4Licence: Unspecified

Cite this

Hosseini, S. S., Wormald, N., & Tian, T. (2020). On Finding the Optimal Tree of a Complete Weighted Graph. In M. Ganzha, L. Maciaszek, & M. Paprzycki (Eds.), Proceedings of the 2020 Federated Conference on Computer Science and Information Systems, FedCSIS 2020 (Vol. 21, pp. 271-275). (Annals of Computer Science and Information Systems; Vol. 21). IEEE, Institute of Electrical and Electronics Engineers. https://doi.org/10.15439/2020F4

Hosseini, Seyed Soheil ; Wormald, Nick ; Tian, Tianhai. / On Finding the Optimal Tree of a Complete Weighted Graph. Proceedings of the 2020 Federated Conference on Computer Science and Information Systems, FedCSIS 2020. editor / Maria Ganzha ; Leszek Maciaszek ; Marcin Paprzycki. Vol. 21 Warsaw Poland : IEEE, Institute of Electrical and Electronics Engineers, 2020. pp. 271-275 (Annals of Computer Science and Information Systems).

@inproceedings{920e4bf60c3a4dd8b036c411559a9dad,

title = "On Finding the Optimal Tree of a Complete Weighted Graph",

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.",

author = "Hosseini, {Seyed Soheil} and Nick Wormald and Tianhai Tian",

year = "2020",

month = sep,

doi = "10.15439/2020F4",

language = "English",

volume = "21",

series = "Annals of Computer Science and Information Systems",

publisher = "IEEE, Institute of Electrical and Electronics Engineers",

pages = "271--275",

editor = "Maria Ganzha and Leszek Maciaszek and Marcin Paprzycki",

booktitle = "Proceedings of the 2020 Federated Conference on Computer Science and Information Systems, FedCSIS 2020",

address = "United States of America",

note = "Federated Conference on Computer Science and Information Systems (FedCSIS) 2020, FedCSIS 2020 ; Conference date: 06-09-2020 Through 09-09-2020",

url = "https://fedcsis.org/2020/, https://ieeexplore.ieee.org/xpl/conhome/9217610/proceeding",

}

Hosseini, SS, Wormald, N & Tian, T 2020, On Finding the Optimal Tree of a Complete Weighted Graph. in M Ganzha, L Maciaszek & M Paprzycki (eds), Proceedings of the 2020 Federated Conference on Computer Science and Information Systems, FedCSIS 2020. vol. 21, Annals of Computer Science and Information Systems, vol. 21, IEEE, Institute of Electrical and Electronics Engineers, Warsaw Poland, pp. 271-275, Federated Conference on Computer Science and Information Systems (FedCSIS) 2020, Virtual, Sofia, Bulgaria, 6/09/20. https://doi.org/10.15439/2020F4

On Finding the Optimal Tree of a Complete Weighted Graph. / Hosseini, Seyed Soheil; Wormald, Nick ; Tian, Tianhai.
Proceedings of the 2020 Federated Conference on Computer Science and Information Systems, FedCSIS 2020. ed. / Maria Ganzha; Leszek Maciaszek; Marcin Paprzycki. Vol. 21 Warsaw Poland: IEEE, Institute of Electrical and Electronics Engineers, 2020. p. 271-275 (Annals of Computer Science and Information Systems; Vol. 21).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - On Finding the Optimal Tree of a Complete Weighted Graph

AU - Hosseini, Seyed Soheil

AU - Wormald, Nick

AU - Tian, Tianhai

N1 - Conference code: 15th

PY - 2020/9

Y1 - 2020/9

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85095748795&partnerID=8YFLogxK

U2 - 10.15439/2020F4

DO - 10.15439/2020F4

M3 - Conference Paper

AN - SCOPUS:85095748795

VL - 21

T3 - Annals of Computer Science and Information Systems

SP - 271

EP - 275

BT - Proceedings of the 2020 Federated Conference on Computer Science and Information Systems, FedCSIS 2020

A2 - Ganzha, Maria

A2 - Maciaszek, Leszek

A2 - Paprzycki, Marcin

PB - IEEE, Institute of Electrical and Electronics Engineers

CY - Warsaw Poland

T2 - Federated Conference on Computer Science and Information Systems (FedCSIS) 2020

Y2 - 6 September 2020 through 9 September 2020

ER -

Hosseini SS, Wormald N , Tian T. On Finding the Optimal Tree of a Complete Weighted Graph. In Ganzha M, Maciaszek L, Paprzycki M, editors, Proceedings of the 2020 Federated Conference on Computer Science and Information Systems, FedCSIS 2020. Vol. 21. Warsaw Poland: IEEE, Institute of Electrical and Electronics Engineers. 2020. p. 271-275. (Annals of Computer Science and Information Systems). doi: 10.15439/2020F4

On Finding the Optimal Tree of a Complete Weighted Graph

Abstract

Publication series

Conference

Access to Document

Other files and links

Cite this