Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > BERNHARD FUCHS:
All reports by Author Bernhard Fuchs:

TR05-113 | 12th September 2005
Bernhard Fuchs

On the Hardness of Range Assignment Problems

We investigate the computational hardness of the {\sc Connectivity},
the {\sc Strong Connectivity} and the {\sc Broadcast} type of Range
Assignment Problems in $\R^2$ and $\R^3$.
We present new reductions for the {\sc Connectivity} problem, which
are easily adapted to suit the other two problems. All reductions
are considerably simpler ... more >>>




ISSN 1433-8092 | Imprint