Premium
A flow‐dependent quadratic steiner tree problem in the Euclidean plane
Author(s) -
Brazil Marcus N.,
Ras Charl J.,
Thomas Doreen A.
Publication year - 2014
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21553
Subject(s) - steiner tree problem , combinatorics , mathematics , bounded function , flow network , spanning tree , cutting plane method , quadratic equation , tree network , discrete mathematics , mathematical optimization , integer programming , time complexity , mathematical analysis , geometry
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 of these nodes and a bounded number of Steiner points, such that∑ e ∈ E ( T ) f ( e ) | e | 2is a minimum, where f ( e ) is the flow on edge e . The edges are uncapacitated and the flows are determined additively, that is, 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 optimize 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. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 64(1), 18–28 2014