Published in:
(S. Nikoletseas and J.D.P. Rolim, eds) Springer Lecture Notes in Computer Science 4240, pp. 176-183, 2006.
In the network localization problem the locations of some
nodes (called anchors) as well as the distances
between some pairs of nodes are known, and the goal is to
determine the location of all nodes.
The localization problem
is said to be solvable (or uniquely localizable)
if there is a unique set of locations
consistent with the given data. Recent results from graph rigidity
theory made it possible to characterize the solvability of
the localization problem in two dimensions.
In this paper we address the following related optimization problem:
given the set of known distances in the network,
make the localization problem solvable
by computing the locations of as few
nodes as possible, that is, by minimizing the number of anchor
nodes.
We develop a polynomial-time 3-approximation algorithm
for this problem by proving new structural results in graph
rigidity and by using tools from matroid theory.
Bibtex entry:
@techreport{egres-06-15,
AUTHOR | = | {Fekete, Zsolt and Jord{\'a}n, Tibor}, |
TITLE | = | {Uniquely localizable networks with few anchors}, |
NOTE | = | {{\tt egres.elte.hu}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2006}, |
NUMBER | = | {TR-2006-15} |