{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:22:07Z","timestamp":1725664927876},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540625599"},{"type":"electronic","value":"9783540680727"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-62559-3_25","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T22:41:08Z","timestamp":1330296068000},"page":"308-322","source":"Crossref","is-referenced-by-count":1,"title":["On the hardness of allocating frequencies for hybrid networks"],"prefix":"10.1007","author":[{"given":"Ewa","family":"Malesi\u0144ska","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alessandro","family":"Panconesi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"key":"25_CR1","doi-asserted-by":"crossref","unstructured":"M.Ajtai. Recursive construction for 3-regular expanders. Proc. 28th Annual IEEE Symp. on Foundations of Computer Science (1987), 295\u2013304.","DOI":"10.1109\/SFCS.1987.50"},{"key":"25_CR2","unstructured":"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."},{"key":"25_CR3","unstructured":"M. Bellare, O. Goldreich, and M. Sudan. Free bits, PCPs and non-approximability \u2014 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\u2013131, 1993."},{"key":"25_CR4","unstructured":"C. Berge. Graphs. North-Holland Math. Library, Vol. 6, Part 1, Elsevier Science Publishers (1985)."},{"key":"25_CR5","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0012-365X(89)90193-3","volume":"74","author":"C. Berge","year":"1989","unstructured":"C. Berge. Minimax relations for the partial q-colorings of a graph. Disc. Mathematics 74 (1989), 3\u201314.","journal-title":"Disc. Mathematics"},{"key":"25_CR6","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"1990","unstructured":"T.H.Cormen, C.E.Leiserson and R.L.Rivest. Introduction to Algorithms. The MIT Press, Cambridge, McGraw Hill, 1990."},{"key":"25_CR7","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1007\/BF02110310","volume":"3","author":"G. Dahl","year":"1994","unstructured":"G. Dahl, K. J\u00f6rnsten, G. L\u00d8vnes, S. Svaet. Graph optimization problems in connection with the management of mobile communication systems. Telecommunications Systems, Vol. 3 (1994), 319\u2013340.","journal-title":"Telecommunications Systems"},{"key":"25_CR8","doi-asserted-by":"crossref","first-page":"526","DOI":"10.1109\/25.260758","volume":"42","author":"D. Dimitrijevi\u0107","year":"1993","unstructured":"D. Dimitrijevi\u0107, J. Vu\u010deti\u0107. Design and Performance Analysis of the Algorithms for Channel Allocation in Cellular Networks. IEEE Transactions on Vehicular Technology, Vol. 42 (1993), 526\u2013534.","journal-title":"IEEE Transactions on Vehicular Technology"},{"key":"25_CR9","unstructured":"A. Gr\u00e4f, M. Stumpf, G. Wei\\enfels. On coloring unit disk graphs. Johannes Gutenberg-Universit\u00e4t Mainz (1994)."},{"key":"25_CR10","doi-asserted-by":"crossref","unstructured":"H. Eriksson, R. Bownds. Performance of Dynamic Channel Allocation in the DECT System. 41st IEEE Vehicular Technology Conference (1991), 693\u2013698.","DOI":"10.1109\/VETEC.1991.140582"},{"key":"25_CR11","doi-asserted-by":"crossref","first-page":"1497","DOI":"10.1109\/PROC.1980.11899","volume":"68","author":"W.K. Hale","year":"1980","unstructured":"W.K. Hale. Frequency Assignment: Theory and Applications. Proc. of the IEEE, Vol. 68 (1980), 1497\u20131514.","journal-title":"Proc. of the IEEE"},{"key":"25_CR12","first-page":"231","volume":"824","author":"J. H\u00e5stad","year":"1994","unstructured":"J. H\u00e5stad. Recent results in hardness of approximation. Proc. of 3rd Scandinavian Workshop on Algorithm Theory (1994), Springer-Verlag LNCS 824, pp. 231\u2013239.","journal-title":"Springer-Verlag LNCS"},{"key":"25_CR13","doi-asserted-by":"crossref","unstructured":"T. Jensen, B. Toft. Graph Coloring Problems. John Wiley & Sons, Inc., 1995.","DOI":"10.1002\/9781118032497"},{"key":"25_CR14","doi-asserted-by":"crossref","unstructured":"E. Malesi\u0144ska. An Optimization Method for the Channel Assignment in Mixed Environments. Proc. of the 1st ACM Int. Conf. on Mobile Computing and Networking (1995), 210\u2013217.","DOI":"10.1145\/215530.215576"},{"key":"25_CR15","doi-asserted-by":"crossref","unstructured":"E. Malesi\u0144ska, A. Panconesi. On the Hardness of Allocating Frequencies for Hybrid Networks. Preprint No. 498\/1996, Fachb. Mathematik, TU Berlin.","DOI":"10.1007\/3-540-62559-3_25"},{"key":"25_CR16","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/net.3230250205","volume":"25","author":"M.V. Marathe","year":"1995","unstructured":"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\u201368.","journal-title":"Networks"},{"key":"25_CR17","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"Ch.H. Papadimitriou, M. Yannakakis. Optimization, Approximation, and Complexity Classes. Journal of Computer and System Sciences 43 (1991), 425\u2013440.","journal-title":"Journal of Computer and System Sciences"},{"key":"25_CR18","unstructured":"J. Plehn. Private communication."},{"key":"25_CR19","volume-title":"RUTCOR Res. Rept. RRR 57-89","author":"B.A. Tesman","year":"1989","unstructured":"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)."},{"key":"25_CR20","doi-asserted-by":"crossref","unstructured":"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\u2013274.","DOI":"10.1007\/978-1-4615-3144-9_15"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-62559-3_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:13:11Z","timestamp":1605647591000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-62559-3_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540625599","9783540680727"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-62559-3_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}