Geometric spanning trees minimizing the Wiener index

DOI10.1007/978-3-031-38906-1_1MaRDI QIDQ6138982zbMATH OpenOpenAlexFDO

Authors A. Karim Abu-Affash, Paz Carmi, Joseph S. B. Mitchell

Publication date 16 January 2024

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2303.01096

zbMATH Keywords

Wiener indexminimum routing cost spanning treeoptimum communication spanning tree

Mathematics Subject Classification ID

Data structures (68P05) Algorithms in computer science (68Wxx)

Abstract: 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.

Recommendations

• Geometric spanning trees minimizing the Wiener index
• scientific article; zbMATH DE number 5619543
• Extremal trees with respect to the Steiner Wiener index
• scientific article; zbMATH DE number 6945760
• Wiener index versus maximum degree in trees

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 508964 (Why is no real title available?)
• scientific article; zbMATH DE number 1947396 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
• A survey on graphs extremal with respect to distance-based topological indices
• Approximating the average stretch factor of geometric graphs
• Approximation algorithms for minimizing average distortion
• EFFICIENT CONSTRUCTION OF LOW WEIGHTED BOUNDED DEGREE PLANAR SPANNER
• Geometric Spanner Networks
• Handbook of Approximation Algorithms and Metaheuristics
• Local properties of geometric graphs
• Mathematical aspects of Wiener index
• Minimum weight Euclidean t-spanner is NP-hard
• On bounded degree plane strong geometric spanners
• On the point for which the sum of the distances to \(n\) given points is minimum
• Optimum Communication Spanning Trees
• Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems
• Survey on geometric-arithmetic indices of graphs
• The complexity of the network design problem
• The greedy spanner is existentially optimal (extended abstract)
• Wiener index of trees: Theory and applications

Cited in

(1)

• Geometric spanning trees minimizing the Wiener index

This page was built for publication: Geometric spanning trees minimizing the Wiener index

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6138982)