TY - JOUR
AU - Abu-Affash, Karim
AU - Carmi, Paz
AU - Luwisch, Ori
AU - Mitchell, Joseph
PY - 2024/03/12
Y2 - 2024/11/07
TI - Geometric Spanning Trees Minimizing the Wiener Index
JF - Computing in Geometry and Topology
JA - CompGeomTop
VL - 3
IS - 1
SE - Original Research Articles
DO - 10.57717/cgt.v3i1.52
UR - https://www.cgt-journal.org/index.php/cgt/article/view/52
SP - 2:1-2:15
AB - <p>The Wiener index of a network, introduced by the chemist Harry Wiener, is the sum of distances between all pairs of nodes in the network. This index, originally used in chemical graph representations of the non-hydrogen atoms of a molecule, is considered to be a fundamental and useful network descriptor. We study the problem of constructing geometric networks on point sets in Euclidean space that minimize the Wiener index: given a set P of n$points in R<sup>d</sup>, the goal is to construct a network, spanning P and satisfying certain constraints, that minimizes the Wiener index among the allowable class of spanning networks.</p><p>In this work, we focus mainly on spanning networks that are trees and we focus on problems in the plane (d = 2). We show that any spanning tree that minimizes the Wiener index has non-crossing edges in the plane. Then, we use this fact to devise an O(n<sup>4</sup>)-time algorithm that constructs a spanning tree of minimum Wiener index for points in convex position. We also prove that the problem of computing a spanning tree on P whose Wiener index is at most W, while having total (Euclidean) weight at most B, is NP-hard.</p><p>Computing a tree that minimizes the Wiener index has been studied in the area of communication networks, where it is known as the <em>minimum routing cost spanning tree problem</em>. </p>
ER -