On the hardness of allocating frequencies for hybrid networks

1. M.Ajtai. Recursive construction for 3-regular expanders. Proc. 28th Annual IEEE Symp. on Foundations of Computer Science (1987), 295–304.

   Google Scholar 

2. S. Arora. Probabilistic checking of proofs and the hardness of approximation problems. PhD Thesis, U.C. Berkeley, 1994. Available via anonymous ftp as Princeton TR94-476.

   Google Scholar 

3. M. Bellare, O. Goldreich, and M. Sudan. Free bits, PCPs and non-approximability — towards tight results. Technical Report ECCC TR95-24, Revised version, September 1995. Extended abstract in Proc. 25th ACM Symp. on Theory of Computing (1993), 113–131, 1993.

   Google Scholar 

4. C. Berge. Graphs. North-Holland Math. Library, Vol. 6, Part 1, Elsevier Science Publishers (1985).

   Google Scholar 

5. C. Berge. Minimax relations for the partial q-colorings of a graph. Disc. Mathematics 74 (1989), 3–14.

   Google Scholar 

6. T.H.Cormen, C.E.Leiserson and R.L.Rivest. Introduction to Algorithms. The MIT Press, Cambridge, McGraw Hill, 1990.

   Google Scholar 

7. G. Dahl, K. Jörnsten, G. LØvnes, S. Svaet. Graph optimization problems in connection with the management of mobile communication systems. Telecommunications Systems, Vol. 3 (1994), 319–340.

   Google Scholar 

8. D. Dimitrijević, J. Vučetić. Design and Performance Analysis of the Algorithms for Channel Allocation in Cellular Networks. IEEE Transactions on Vehicular Technology, Vol. 42 (1993), 526–534.

   Google Scholar 

9. A. Gräf, M. Stumpf, G. Wei\enfels. On coloring unit disk graphs. Johannes Gutenberg-Universität Mainz (1994).

   Google Scholar 

10. H. Eriksson, R. Bownds. Performance of Dynamic Channel Allocation in the DECT System. 41st IEEE Vehicular Technology Conference (1991), 693–698.

    Google Scholar 

11. W.K. Hale. Frequency Assignment: Theory and Applications. Proc. of the IEEE, Vol. 68 (1980), 1497–1514.

    Google Scholar 

12. J. Håstad. Recent results in hardness of approximation. Proc. of 3rd Scandinavian Workshop on Algorithm Theory (1994), Springer-Verlag LNCS 824, pp. 231–239.

    Google Scholar 

13. T. Jensen, B. Toft. Graph Coloring Problems. John Wiley & Sons, Inc., 1995.

    Google Scholar 

14. E. Malesińska. An Optimization Method for the Channel Assignment in Mixed Environments. Proc. of the 1st ACM Int. Conf. on Mobile Computing and Networking (1995), 210–217.

    Google Scholar 

15. E. Malesińska, A. Panconesi. On the Hardness of Allocating Frequencies for Hybrid Networks. Preprint No. 498/1996, Fachb. Mathematik, TU Berlin.

    Google Scholar 

16. M.V. Marathe, H. Breu, H.B. Hunt III, S.S. Ravi, D.J. Rosenkrantz. Simple Heuristics for Unit Disk Graphs. Networks, Vol.25 (1995), 59–68.

    Google Scholar 

17. Ch.H. Papadimitriou, M. Yannakakis. Optimization, Approximation, and Complexity Classes. Journal of Computer and System Sciences 43 (1991), 425–440.

    Google Scholar 

18. J. Plehn. Private communication.

    Google Scholar 

19. B.A. Tesman. T-colorings, list T-colorings, and set T-colorings of graphs. RUTCOR Res. Rept. RRR 57-89 Rutgers University, New Brunswick, NJ (1989).

    Google Scholar 

20. J. Zander, H. Eriksson. Asymptotic Bounds on the Performance of a Class of Dynamic Channel Assignment Algorithms. Wireless communications: future directions, ed. by J.M. Holtzman, D.J. Goodman, Kluwer Ac. Publ. (1993), 259–274.

    Google Scholar 

Download references