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 >>>

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 >>>