{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T12:34:39Z","timestamp":1743078879567,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540440406"},{"type":"electronic","value":"9783540456872"}],"license":[{"start":{"date-parts":[[2002,1,1]],"date-time":"2002-01-01T00:00:00Z","timestamp":1009843200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2002,1,1]],"date-time":"2002-01-01T00:00:00Z","timestamp":1009843200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45687-2_6","type":"book-chapter","created":{"date-parts":[[2007,10,19]],"date-time":"2007-10-19T08:57:47Z","timestamp":1192784267000},"page":"81-92","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On Radiocoloring Hierarchically Specified Planar Graphs: $$ \\mathcal{P}\\mathcal{S}\\mathcal{P}\\mathcal{A}\\mathcal{C}\\mathcal{E} $$ -Completeness and Approximations"],"prefix":"10.1007","author":[{"given":"Maria I.","family":"Andreou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dimitris A.","family":"Fotakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sotiris E.","family":"Nikoletseas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vicky G.","family":"Papadopoulou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul G.","family":"Spirakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,10,4]]},"reference":[{"key":"6_CR1","unstructured":"Geir Agnarsson, Magnus M.Halld\u00f3rsson: Coloring Powers of Planar Graphs. ACM Symposium on Discrete Algorithms (SODA) (2000)."},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"M.I. Andreou, D.A. Fotakis, S.E. Nikoletseas, V.G. Papadopoulou and P.G. Spirakis: On Radiocoloring Hierarchically Specified Planar Graphs: $$\n\\mathcal{P}\\mathcal{S}\\mathcal{P}\\mathcal{A}\\mathcal{C}\\mathcal{E}\n$$\n-completeness and Approximations (full version). CTI Technichal Report 2002, URL http:\/\/students.ceid.upatras.gr\/~viki.","DOI":"10.1007\/3-540-45687-2_6"},{"key":"6_CR3","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B. S. Baker","year":"1994","unstructured":"B. S. Baker: Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM 41:153\u2013180, 1994.","journal-title":"Journal of the ACM"},{"key":"6_CR4","volume-title":"TR RUU-CS-88-14","author":"H.L. Bodlaender","year":"1988","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":"6_CR5","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1007\/3-540-46541-3_33","volume-title":"Proc. 17th Annual Symp. on Theoretical Aspects of Computer Science (STACS)","author":"H.L. Bodlaender","year":"2000","unstructured":"Bodlaender, H.L., T. Kloks, R.B. Tan and J. van Leeuwen: Approximations for \u03bb-coloring of graphs. In Proc. 17th Annual Symp. on Theoretical Aspects of Computer Science (STACS). LNCS Vol. 1770, pp. 395\u2013406, 2000."},{"key":"6_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1007\/3-540-44612-5_32","volume-title":"Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science (MFCS)","author":"D.A. Fotakis","year":"2000","unstructured":"D.A. Fotakis, S.E. Nikoletseas, V.G. Papadopoulou and P.G. Spirakis: completeness Results and Efficient Approximations for Radiocoloring in Planar Graphs. In Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science (MFCS), Editors Mogens Nielsen, Branislav Rovan, LNCS 1893, pp 363\u2013372, 2000."},{"key":"6_CR7","unstructured":"M. R. Garey, D. S. Johnson: \u201cComputers and Intractability: A guide to the Theory of NP-completeness\u201d, W. H.\/ Freeman and Company, 1979."},{"key":"6_CR8","unstructured":"Krumke, M.V. Marathe and S. S. Ravi: 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":"6_CR9","doi-asserted-by":"publisher","first-page":"474","DOI":"10.1145\/65950.65952","volume":"36","author":"T. Lengauer","year":"1989","unstructured":"T. Lengauer: Hierarchical Planarity Testing. Journal of ACM, Vol 36, No 3, pp. 474\u2013509, (1989).","journal-title":"Journal of ACM"},{"key":"6_CR10","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0022-0000(92)90004-3","volume":"44","author":"T. Lengauer","year":"1992","unstructured":"T. Lengauer and K.W. Wagner: Correlation between the Complexities of the Of hierarchical and Hierarchical Versions of graph Problems. Journal of Computer and System Sciences, 44, pp. 63\u201393 (1992).","journal-title":"Journal of Computer and System Sciences"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"M.V. Marathe, H.B. Hunt III, R.E. Stearns and V. Radhakrishnan: Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems. Proc. 26th Annual ACM Symposium on the Theory of Computing (STOC), pp. 468\u2013478, May 1994. A complete version appears in SIAM Journal on Computing, Vol. 27, No 5, Oct. 1998, pp. 1237\u20131261.","DOI":"10.1137\/S0097539795285254"},{"key":"6_CR12","unstructured":"H. Marathe, H. Hunt III, R. Stearns and V. Radhakrishnan: \u201cComplexity of hier-achically and 1-dimensioned periodically specified problems\u201d. DIMACS Workshop on Satisfiability Problem: Theory and Applications (1996)."},{"key":"6_CR13","series-title":"Lect Notes Comput Sci","first-page":"21","volume-title":"Proc. 19th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)","author":"M.V. Marathe","year":"1993","unstructured":"M.V. Marathe, V. Radhakrishnan, H.B. Hunt III and S.S. Ravi: Hierarchically Specified Unit Disk Graphs. Proc. 19th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Utrecht, Netherlands, LNCS 790, pp. 21\u201332, Springer Verlag, (June 1993). Journal version appears in Theoretical Computer Science, 174(1\u20132), pp. 23\u201365, (March 1997)."},{"key":"6_CR14","doi-asserted-by":"crossref","unstructured":"S. T. McCormick: Optimal approximation of sparse hessians and its equivalence to a graph coloring problem. Technical Report SOL 81-22, Dept. of Operations Research, Standford University, 1981.","DOI":"10.21236\/ADA110846"},{"key":"6_CR15","unstructured":"S. Ramanathan, E. R. Loyd: The complexity of distance2-coloring. 4th International Conference of Computing and information, (1992) 71\u201374."},{"key":"6_CR16","unstructured":"X. Zhou, Y. Kanari, T. Nishizeki: Generalized vertex-coloring of partial k-trees. IEICE Trans. Foundamentals, EXX-A(1), 2000."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2002"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45687-2_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,16]],"date-time":"2023-02-16T19:19:39Z","timestamp":1676575179000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/3-540-45687-2_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540440406","9783540456872"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-45687-2_6","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]},"assertion":[{"value":"4 October 2002","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}