{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T08:37:46Z","timestamp":1742978266290,"version":"3.40.3"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319240237"},{"type":"electronic","value":"9783319240244"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-24024-4_8","type":"book-chapter","created":{"date-parts":[[2015,9,4]],"date-time":"2015-09-04T08:00:10Z","timestamp":1441353610000},"page":"97-132","source":"Crossref","is-referenced-by-count":0,"title":["On Radiocoloring Hierarchically Specified Planar Graphs: $$\\mathcal{PSPACE}$$ -completeness and Approximations"],"prefix":"10.1007","author":[{"given":"Maria","family":"Andreou","sequence":"first","affiliation":[]},{"given":"Dimitris","family":"Fotakis","sequence":"additional","affiliation":[]},{"given":"Vicky Papadopoulou","family":"Lesta","sequence":"additional","affiliation":[]},{"given":"Sotiris","family":"Nikoletseas","sequence":"additional","affiliation":[]},{"given":"Paul","family":"Spirakis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,11,22]]},"reference":[{"issue":"4","key":"8_CR1","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1137\/S0895480100367950","volume":"16","author":"G Agnarsson","year":"2003","unstructured":"Agnarsson, G., Halld\u00f3rsson, M.M.: Coloring powers of planar graphs. SIAM J. Discrete Math. 16(4), 651\u2013662 (2003)","journal-title":"SIAM J. Discrete Math."},{"key":"8_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/3-540-45687-2_6","volume-title":"Mathematical Foundations of Computer Science 2002","author":"MI Andreou","year":"2002","unstructured":"Andreou, M.I., Fotakis, D.A., Nikoletseas, S.E., Papadopoulou, V.G., Spirakis, P.G.: On radiocoloring hierarchically specified planar graphs: \n \n \n \n $${{\\cal {P}SPACE}}$$\n -Completeness and approximations. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol. 2420, pp. 81\u201392. Springer, Heidelberg (2002)"},{"key":"8_CR3","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"BS Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41, 153\u2013180 (1994)","journal-title":"J. ACM"},{"key":"8_CR4","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/BF01840379","volume":"5","author":"D Bienstoc","year":"1990","unstructured":"Bienstoc, D., Monma, C.L.: On the complexity of embedding planar graphs to minimize certain distance measures. Algorithmica 5, 93\u2013109 (1990)","journal-title":"Algorithmica"},{"key":"8_CR5","unstructured":"Bodlaender, H.L.: Planar graphs with bounded treewidth. TR RUU-CS-88-14, Department of Computer Science, University of Utrecht, The Netherlands, March 1988"},{"key":"8_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/3-540-46541-3_33","volume-title":"STACS 2000","author":"HL Bodlaender","year":"2000","unstructured":"Bodlaender, H.L., Kloks, T., Tan, R.B., van Leeuwen, J.: \n \n \n \n $$\\lambda $$\n -Coloring of Graphs. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol. 1770, pp. 395\u2013406. Springer, Heidelberg (2000)"},{"key":"8_CR7","unstructured":"Borodin, O.V., Broersma, H.J., Glebov, A., van den Heuvel, J.: Stars and bunches in planar graphs. Part II: General planar graphs and colourings. CDAM Research Report 2002\u20132005 (2002)"},{"key":"8_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1007\/3-540-45995-2_24","volume-title":"LATIN 2002: Theoretical Informatics","author":"T Calamoneri","year":"2002","unstructured":"Calamoneri, T., Petreschi, R.: \n \n \n \n $$L(2,1)$$\n -Coloring Matrogenic Graphs. In: Rajsbaum, S. (ed.) LATIN 2002. LNCS, vol. 2286, pp. 236\u2013247. Springer, Heidelberg (2002)"},{"key":"8_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/3-540-44612-5_32","volume-title":"Mathematical Foundations of Computer Science 2000","author":"DA Fotakis","year":"2000","unstructured":"Fotakis, D.A., Nikoletseas, S.E., Papadopoulou, V.G., Spirakis, P.G.: NP-completeness results and efficient approximations for radiocoloring in planar graphs. In: Nielsen, M., Rovan, B. (eds.) MFCS 2000. LNCS, vol. 1893, pp. 363\u2013372. Springer, Heidelberg (2000)"},{"key":"8_CR10","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1016\/j.tcs.2005.03.013","volume":"340","author":"D Fotakis","year":"2005","unstructured":"Fotakis, D., Nikoletseas, S., Papadopoulou, V.G., Spirakis, P.G.: Radiocoloring in planar graphs: complexity and approximations. Theoret. Comput. Sci. 340, 514\u2013538 (2005). Elsevier","journal-title":"Theoret. Comput. Sci."},{"key":"8_CR11","doi-asserted-by":"crossref","unstructured":"Fotakis, D., Pantziou, G., Pentaris, G., Spirakis, P.: Frequency assignment in mobile and radio networks. In: Networks in Distributed Computing, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 45, pp. 73\u201390. American Mathematical Society, Providence (1999)","DOI":"10.1090\/dimacs\/045\/04"},{"key":"8_CR12","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1, 237\u2013267 (1976)","journal-title":"Theor. Comput. Sci."},{"key":"8_CR13","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A guide to the Theory of NP-completeness. W.H.\/Freeman and Company (1979)"},{"key":"8_CR14","unstructured":"Griggs, J., Liu, D.: Minimum span channel assignments. Recent Advances in Radio Channel Assignments, Invited Minisymposium, Discrete Mathematics (1998)"},{"key":"8_CR15","doi-asserted-by":"publisher","first-page":"586","DOI":"10.1137\/0405048","volume":"5","author":"JR Griggs","year":"1992","unstructured":"Griggs, J.R., Yeh, R.K.: Labeling graphs with a condition at distance 2. SIAM J. Disc. Math. 5, 586\u2013595 (1992)","journal-title":"SIAM J. Disc. Math."},{"key":"8_CR16","unstructured":"Jonas, T.K.: Graph Coloring Analogues With a Condition at Distance Two: L(2, 1)- Labelings and List \n \n \n \n $$\\lambda $$\n -Labelings. Ph.D. thesis, Department of Mathematics, University of South Carolina, Columbia, SC (1993)"},{"key":"8_CR17","unstructured":"Harary, F.: Private communication to Paul Spirakis"},{"issue":"2","key":"8_CR18","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1002\/jgt.10077","volume":"42","author":"J Heuvel Van den","year":"2003","unstructured":"Van den Heuvel, J., McGuinness, S.: Coloring the square of a planar graph. J. Graph Theory 42(2), 110\u2013124 (2003)","journal-title":"J. Graph Theory"},{"key":"8_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"468","DOI":"10.1007\/3-540-57960-5","volume-title":"Algorithms - ESA \u201994","author":"HB Hunt III","year":"1994","unstructured":"Hunt III, H.B., Marathe, M.V., Radhakrishnan, V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol. 855, pp. 468\u2013477. Springer, Heidelberg (1994)"},{"key":"8_CR20","unstructured":"Krumke, Marathe, M.V., Ravi, S.S.: Approximation algorithms for channel assignment in radio networks. In: DIALM for Mobility, 2nd International Workshop on Discrete Algorithms and methods for Mobile Computing and Communications, Dallas, Texas (1998)"},{"issue":"3","key":"8_CR21","doi-asserted-by":"publisher","first-page":"474","DOI":"10.1145\/65950.65952","volume":"36","author":"T Lengauer","year":"1989","unstructured":"Lengauer, T.: Hierarchical planarity testing. J. ACM 36(3), 474\u2013509 (1989)","journal-title":"J. ACM"},{"key":"8_CR22","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0022-0000(92)90004-3","volume":"44","author":"T Lengauer","year":"1992","unstructured":"Lengauer, T., Wagner, K.W.: Correlation between the complexities of the of hierarchical and hierarchical versions of graph problems. J. Comput. Syst. Sci. 44, 63\u201393 (1992)","journal-title":"J. Comput. Syst. Sci."},{"key":"8_CR23","doi-asserted-by":"crossref","unstructured":"Marathe, M.V., Hunt III, H.B., Stearns, R.E., Radhakrishnan, V.: Approximation algorithms for PSPACE-hard hierarchically and periodically specified problems. In: Proceedings of the 26th Annual ACM Symposium on the Theory of Computing (STOC), pp. 468\u2013478, May 1994. A complete version appears in SIAM Journal on Computing 27(5), 1237\u20131261 (1998)","DOI":"10.1137\/S0097539795285254"},{"key":"8_CR24","unstructured":"Marathe, H., Hunt III, H., Stearns, R., Radhakrishnan, V.: Complexity of hierachically and 1-dimensioned periodically specified problems. In: Theory and Applications, DIMACS Workshop on Satisfiability Problem (1996)"},{"key":"8_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/3-540-57899-4_38","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"MV Marathe","year":"1994","unstructured":"Marathe, M.V., Radhakrishnan, V., Hunt III, H.B., Ravi, S.S.: Hierarchically specified unit disk graphs. In: van Leeuwen, J. (ed.) WG 1993. LNCS, vol. 790, pp. 21\u201332. Springer, Heidelberg (1994). Journal version appears in Theoretical Computer Science, 174(1-2), pp. 23-65, March 1997"},{"key":"8_CR26","doi-asserted-by":"crossref","unstructured":"McCormick, S.T.: Optimal approximation of sparse hessians and its equivalence to a graph coloring problem. Technical Report SOL 81\u201322, Department of Operations Research, Standford University (1981)","DOI":"10.21236\/ADA110846"},{"key":"8_CR27","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/j.jctb.2004.12.005","volume":"94","author":"M Molloy","year":"2005","unstructured":"Molloy, M., Salavatipour, M.R.: A bound on the chromatic number of the square of a planar graph. J. Combin. Theory Ser. B 94, 189\u2013213 (2005)","journal-title":"J. Combin. Theory Ser. B"},{"key":"8_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"736","DOI":"10.1007\/3-540-45749-6_64","volume-title":"Algorithms - ESA 2002","author":"M Molloy","year":"2002","unstructured":"Molloy, M., Salavatipour, M.R.: Frequency channel assignment on planar networks. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 736\u2013747. Springer, Heidelberg (2002)"},{"key":"8_CR29","unstructured":"Ramanathan,S., Loyd, E.R.: The complexity of distance2-coloring. In: 4th International Conference of Computing and information, pp. 71\u201374 (1992)"},{"key":"8_CR30","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1137\/S0895480191223178","volume":"7","author":"D Sakai","year":"1994","unstructured":"Sakai, D.: Labeling chordal graphs: distance two condition. SIAM J. Discrete Math. 7, 133\u2013140 (1994)","journal-title":"SIAM J. Discrete Math."},{"key":"8_CR31","unstructured":"Zhou, X., Kanari, Y., Nishizeki, T.: Generalized vertex-coloring of partial k-trees. IEICE Trans. Foundamentals EXX-A(1) (2000)"}],"container-title":["Lecture Notes in Computer Science","Algorithms, Probability, Networks, and Games"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-24024-4_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T17:54:12Z","timestamp":1559238852000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-24024-4_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319240237","9783319240244"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-24024-4_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}