Geometric Spanning Trees Minimizing the Wiener Index
Geometric Spanning Trees Minimizing the Wiener Index
复制标题
DOI：
10.48550/arxiv.2303.01096
复制
发表时间：
2023-03
期刊：
影响因子：
--
通讯作者：
A. K. Abu-Affash;Paz Carmi;Ori Luwisch;Joseph S. B. Mitchell
中科院分区：
文献类型：
--
作者：
A. K. Abu-Affash;Paz Carmi;Ori Luwisch;Joseph S. B. Mitchell
由化学家Harry Wiener提出的网络的Wiener指数是网络中所有节点对之间的距离之和。该指数最初用于分子的非氢原子的化学图形表示，被认为是一个基本的和有用的网络描述符。我们研究在欧几里得空间中的点集上构造几何网络以使Wiener指数最小化的问题：给定$\mathbb{R}^d$中$n$个点的集合$P$，目标是构造一个网络，跨越$P$并满足某些约束，在允许的一类跨越网络中最小化Wiener指数。在这项工作中，我们主要集中在生成网络是树，我们专注于在平面上的问题（$d=2$）。我们表明，任何生成树，最大限度地减少维纳指数有非交叉的边缘在平面上。然后，我们利用这一事实，设计了一个$O（n^4）$时间算法，构造一个最小维纳指数的生成树的凸位置的点。我们还证明了问题的计算生成树$P$的维纳指数是最多$W$，而总（欧几里德）重量最多$B$，是NP-困难的。计算一棵树，使维纳指数最小化已经在通信网络领域进行了研究，在那里它被称为最佳通信生成树问题。
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 $\mathbb{R}^d$, 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. 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^4)$-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. Computing a tree that minimizes the Wiener index has been studied in the area of communication networks, where it is known as the optimum communication spanning tree problem.