5
$\begingroup$

Given $n$ nodes in the plane, connect the nodes by a spanning tree. For each node $v$ we construct a disk centered at $v$ with radius equal to the distance to $v$’s furthest neighbor in the spanning tree. The interference of a node $v$ is then defined as the number of such disks that include the node $v$.

The problem I'm interested is to find a spanning tree that minimizes the maximum interference.

What is known about the problem in terms of computational complexity? Is it NP-hard? Can it be solved efficiently? What is its inapproximability threshold?

Apparently this problem is still not understood well. I do not know the complexity of the problem (solvable optimally in polynomial time, or NP-complete), and as far as I know it is unknown whether efficient approximation algorithms exist.

$\endgroup$
2
$\begingroup$

This problem already is known, and is NP-Hard, but if you like to know more about the interference related problems I'd offer you to read this book.

The Problem 1, in the Buchin work is as follow:

Problem 1 (Locher, von Rickenbach, Wattenhofer[5]). Given n nodes in the plane. Connect the nodes by a spanning tree. For each node v we construct a disk centering at v with radius equal to the distance to v's furthest neighbor in the spanning tree. The interference of a node v is then defined as the number of disks that include node v (not counting the disk of v itself ). Find a spanning tree that minimizes the maximum interference.

$\endgroup$
  • $\begingroup$ give some idea about solution. $\endgroup$ – Manish Kumar May 4 '14 at 0:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.