Geometric spanning trees minimizing the Wiener index

DOI10.1007/978-3-031-38906-1_1arXiv2303.01096OpenAlexW4385317362MaRDI QIDQ6138982FDOQ6138982

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)

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.

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

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

zbMATH Keywords

Wiener indexminimum routing cost spanning treeoptimum communication spanning tree

Mathematics Subject Classification ID

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

Cites Work

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

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)