|
We consider rigid and globally rigid bar-and-joint
frameworks (resp. graphs) in which some joints (resp.
vertices) are pinned down and hence their positions are fixed.
We give an overview of some old and new results of this
branch of combinatorial rigidity with an emphasis on
the related optimization problems.
In one of these problems the goal is to find a
set P of vertices of minimum total cost
for which the positions of all vertices become uniquely
determined when P is pinned down.
For this problem, which is motivated by the
localization problem in wireless sensor networks, we give a constant
factor approximation algorithm.
Bibtex entry:
| AUTHOR | = | {Jord{\'a}n, Tibor}, |
| TITLE | = | {Rigid and Globally Rigid Graphs with Pinned Vertices}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2009}, |
| NUMBER | = | {TR-2009-05} |