
Proceedings Paper
Constructing minimum-cost flow-dependent networksFormat | Member Price | Non-Member Price |
---|---|---|
$17.00 | $21.00 |
Paper Abstract
In the construction of a communication network, the length of the
network is an important but not unique factor determining the cost
of the network. Among many possible network models, Gilbert
proposed a flow-dependent model in which flow demands are assigned
between each pair of points in a given point set A, and the cost per unit length of a link in the network is a function of the flow through the link. In this paper we first investigate the
properties of this Gilbert model: the concavity of the cost
function, decomposition, local minimality, the number of Steiner
points and the maximum degree of Steiner points. Then we propose
three heuristics for constructing minimum cost Gilbert networks.
Two of them come from the fact that generally a minimum cost
Gilbert network stands between two extremes: the complete network
G(A) on A and the edge-weighted Steiner minimal tree W(A) on A. The first heuristic starts with $G(A)$ and reduces the cost by splitting angles; the second one starts with both G(A) and W(A), and reduces the cost by selecting low cost paths. As a generalisation of the second heuristic, the third heuristic
constructs a new Gilbert network of less cost by hybridising known
Gilbert networks. Finally we discuss some considerations in
practical applications.
Paper Details
Date Published: 29 August 2002
PDF: 9 pages
Proc. SPIE 4909, Network Design and Management, (29 August 2002); doi: 10.1117/12.481078
Published in SPIE Proceedings Vol. 4909:
Network Design and Management
Qian Mao; Shoa-Kai Liu; Kwok-wai Cheung, Editor(s)
PDF: 9 pages
Proc. SPIE 4909, Network Design and Management, (29 August 2002); doi: 10.1117/12.481078
Show Author Affiliations
Doreen A. Thomas, Univ. of Melbourne (Australia)
Jia Feng Weng, Univ. of Melbourne (Australia)
Published in SPIE Proceedings Vol. 4909:
Network Design and Management
Qian Mao; Shoa-Kai Liu; Kwok-wai Cheung, Editor(s)
© SPIE. Terms of Use
