|
Published in:
A $d$-dimensional framework is a pair $(G,p)$, where $G=(V,E)$ is a graph and $p$ is a map from $V$ to $\mathbb{R}^d$. The length of an edge of $G$ is equal to the distance between the points corresponding to its end-vertices. The framework is said to be globally rigid if its edge lengths uniquely determine all pairwise distances in the framework. A graph $G$ is called globally rigid in $\mathbb{R}^d$ if every generic $d$-dimensional framework $(G,p)$ is globally rigid. Global rigidity has applications in wireless sensor network localization, molecular conformation, formation control, CAD, and elsewhere. \newline Motivated by these applications we consider the following optimization problem: given a graph $G=(V,E)$, a non-negative cost function $c:E\to \mathbb{R}_{+}$ on the edge set of $G$, and a positive integer $d$. Find a subgraph $H=(V,E')$ of $G$, on the same vertex set, which is globally rigid in $\mathbb{R}^d$ and for which the total cost $c(E'):=\sum_{e\in E'} c(e)$ of the edges is as small as possible. This problem is NP-hard for all $d\geq 1$, even if $c$ is uniform or $G$ is complete and $c$ is metric. We focus on the two-dimensional case, where we give $\frac{3}{2}$-approximation (resp. $2$-approximation) algorithms for the uniform cost and metric versions. We also develop a constant factor approximation algorithm for the metric version of the $d$-dimensional problem, for every $d\geq 3$.
Bibtex entry:
| AUTHOR | = | {Jord{\'a}n, Tibor and Mih{\'a}lyk{\'o}, Andr{\'a}s}, |
| TITLE | = | {Minimum Cost Globally Rigid Subgraphs}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2019}, |
| NUMBER | = | {TR-2019-01} |