@article{Abu-Affash_Carmi_Luwisch_Mitchell_2024, title={Geometric Spanning Trees Minimizing the Wiener Index}, volume={3}, url={https://www.cgt-journal.org/index.php/cgt/article/view/52}, DOI={10.57717/cgt.v3i1.52}, abstractNote={<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>}, number={1}, journal={Computing in Geometry and Topology}, author={Abu-Affash, Karim and Carmi, Paz and Luwisch, Ori and Mitchell, Joseph}, year={2024}, month={Mar.}, pages={2:1–2:15} }