Mathematics – Metric Geometry
Scientific paper
2011-11-09
Mathematics
Metric Geometry
Scientific paper
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 $\displaystyle\sum_{e \in E(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.
Brazil Marcus
Ras Charl
Thomas Doreen
No associations
LandOfFree
A Flow-dependent Quadratic Steiner Tree Problem in the Euclidean Plane does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Flow-dependent Quadratic Steiner Tree Problem in the Euclidean Plane, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Flow-dependent Quadratic Steiner Tree Problem in the Euclidean Plane will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-41665