A flow-dependent quadratic Steiner tree problem in the Euclidean plane

DOI10.1002/NET.21553zbMATH Open1390.90151DBLPjournals/networks/BrazilRT14arXiv1111.2109OpenAlexW1986918391WikidataQ61714585 ScholiaQ61714585MaRDI QIDQ4642476FDOQ4642476

Authors: M. Brazil, C. J. Ras, D. A. Thomas 

Publication date: 23 May 2018

Published in: Networks (Search for Journal in Brave)

Abstract: We introduce a flow-dependent version of the quadratic Steiner tree problem in the plane. An instance of the problem on a set of embedded sources and a sink asks for a directed tree $T$ spanning these nodes and a bounded number of Steiner points, such that $displaystylesu{m}_{einE(T)}f(e)|e{|}^2$ is a minimum, where $f(e)$ is the flow on edge $e$. The edges are uncapacitated and the flows are determined additively, i.e., the flow on an edge leaving a node $u$ will be the sum of the flows on all edges entering $u$. Our motivation for studying this problem is its utility as a model for relay augmentation of wireless sensor networks. In these scenarios one seeks to optimise power consumption -- which is predominantly due to communication and, in free space, is proportional to the square of transmission distance -- in the network by introducing additional relays. We prove several geometric and combinatorial results on the structure of optimal and locally optimal solution-trees (under various strategies for bounding the number of Steiner points) and describe a geometric linear-time algorithm for constructing such trees with known topologies.

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

Recommendations

• scientific article; zbMATH DE number 1202981
• An approximation algorithm for a bottleneck \(k\)-Steiner tree problem in the Euclidean plane
• On the Euclidean bottleneck full Steiner tree problem
• Optimal interconnection trees in the plane. Theory, algorithms and applications
• Augmenting Euclidean Networks—the Steiner Case

zbMATH Keywords

network flowswireless sensor networksrelay augmentationSteiner arborescencequadratic-cost trees

Mathematics Subject Classification ID

Environmental economics (natural resource models, harvesting, pollution, etc.) (91B76) Communication networks in operations research (90B18)

Cited In (3)

• Angle-restricted Steiner arborescences for flow map layout
• Angle-Restricted Steiner Arborescences for Flow Map Layout
• Simplifying obstacles for Steiner network problems in the plane

This page was built for publication: A flow-dependent quadratic Steiner tree problem in the Euclidean plane

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