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

DOI10.1002/NET.21553MaRDI QIDQ4642476zbMATH OpenOpenAlexDBLPWikidataFDO

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

Publication date 23 May 2018

Published in Networks (Search for Journal in Brave)

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

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)

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.

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

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)