All reports by Author An Zhu:

__
TR06-041
| 6th March 2006
__

Tomas Feder, Rajeev Motwani, An Zhu#### k-connected spanning subgraphs of low degree

__
TR06-040
| 6th March 2006
__

Tomas Feder, Gagan Aggarwal, Rajeev Motwani, An Zhu#### Channel assignment in wireless networks and classification of minimum graph homomorphism

Tomas Feder, Rajeev Motwani, An Zhu

We consider the problem of finding a $k$-vertex ($k$-edge)

connected spanning subgraph $K$ of a given $n$-vertex graph $G$

while minimizing the maximum degree $d$ in $K$. We give a

polynomial time algorithm for fixed $k$ that achieves an $O(\log

n)$-approximation. The only known previous polynomial algorithms

achieved degree $d+1$ ...
more >>>

Tomas Feder, Gagan Aggarwal, Rajeev Motwani, An Zhu

We study the problem of assigning different communication channels to

acces points in a wireless Local Area Network. Each access point will

be assigned a specific radio frequency channel. Since channels with

similar frequencies interfere, it is desirable to assign far apart

channels (frequencies) to nearby access points. Our goal ...
more >>>