{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T20:53:03Z","timestamp":1743108783118,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540578994"},{"type":"electronic","value":"9783540483854"}],"license":[{"start":{"date-parts":[[1994,1,1]],"date-time":"1994-01-01T00:00:00Z","timestamp":757382400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-57899-4_38","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T08:41:02Z","timestamp":1330245662000},"page":"21-32","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Hierarchically specified unit disk graphs"],"prefix":"10.1007","author":[{"given":"M. V.","family":"Marathe","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"V.","family":"Radhakrishnan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"suffix":"III","given":"H. B.","family":"Hunt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S. S.","family":"Ravi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"key":"3_CR1","unstructured":"J.L. Bentley, T. Ottmann, P. Widmayer, \u201cThe Complexity of Manipulating Hierarchically Defined set of Intervals,\u201d Advances in Computing Research, ed. F.P. Preparata Vol. 1, (1983), pp. 127\u2013158."},{"key":"3_CR2","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"B. N. Clark","year":"1990","unstructured":"B.N. Clark, C.J. Colbourn, D.S. Johnson, \u201cUnit Disk Graphs\u201d Discrete Mathematics, 86(1990), pp. 165\u2013177.","journal-title":"Discrete Mathematics"},{"key":"3_CR3","unstructured":"H.B. Hunt III, V. Radhakrishnan, R.E. Stearns \u201cOn The Complexity of Generalized Satisfiability and Hierarchically Specified Generalized Satisfiability Problems,\u201d in preparation."},{"issue":"No.3","key":"3_CR4","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(81)90111-3","volume":"12","author":"R. J. Fowler","year":"1981","unstructured":"R.J. Fowler, M.S. Paterson, S.L. Tanimoto, \u201cOptimal Packing and Covering in the Plane are NP-Complete,\u201d Information Processing Letters, Vol 12, No.3, June 1981, pp. 133\u2013137.","journal-title":"Information Processing Letters"},{"key":"3_CR5","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/S0019-9958(83)80004-7","volume":"56","author":"H. Galperin","year":"1983","unstructured":"H. Galperin and A. Wigderson, \u201cSuccinct Representation of Graphs,\u201d Information and Control, Vol.56, 1983, pp. 183\u2013198.","journal-title":"Information and Control"},{"key":"3_CR6","unstructured":"C. Ghezzi, M. Jazayeri, D. Mandrioli, Fundamentals of Software Engineering, Prentice Hall, Englewood Cliffs, NJ."},{"key":"3_CR7","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, \u201cFrequency Assignment: Theory and Applications,\u201d Proc. IEEE, Vol. 68, 1980, pp 1497\u20131514.","journal-title":"Proc. IEEE"},{"issue":"No.1","key":"3_CR8","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1145\/2455.214106","volume":"32","author":"D. S. Hochbaum","year":"1985","unstructured":"D. S. Hochbaum, W. Mass, \u201cApproximation Schemes for Covering and Packing Problems in Image Processing and VLSI,\u201d JACM, Vol. 32,No. 1, 1985, pp 130\u2013136.","journal-title":"JACM"},{"key":"3_CR9","doi-asserted-by":"crossref","unstructured":"F. H\u00f6fting, T. Lengauer and E. Wanke, \u201cProcessing of Hierarchically Defined Graphs and Graph Families\u201d, in Data Structures and Efficient Algorithms (Final Report on the DFG Special Joint Initiative), LNCS 594, Springer-Verlag, 1992, pp. 44\u201369.","DOI":"10.1007\/3-540-55488-2_21"},{"key":"3_CR10","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1109\/JSAC.1984.1146097","volume":"2","author":"K. Kammerlander","year":"1984","unstructured":"K. Kammerlander, \u201cC 900 \u2014 An Advanced Mobile Radio Telephone System with Optimum Frequency Utilization,\u201d IEEE Trans. Selected Areas in Communication, Vol. 2, 1984, pp 589\u2013597.","journal-title":"IEEE Trans. Selected Areas in Communication"},{"issue":"No.6","key":"3_CR11","doi-asserted-by":"crossref","first-page":"1063","DOI":"10.1137\/0217068","volume":"17","author":"T. Lengauer","year":"1988","unstructured":"T. Lengauer, E. Wanke, \u201cEfficient Solutions for Connectivity Problems for Hierarchically Defined Graphs,\u201d SIAM J. Computing, Vol. 17, No. 6, 1988, pp. 1063\u20131080.","journal-title":"SIAM J. Computing"},{"key":"3_CR12","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1016\/0196-6774(87)90042-3","volume":"8","author":"T. Lengauer","year":"1987","unstructured":"T. Lengauer, \u201cEfficient Algorithms for Finding Minimum Spanning Forests of Hierarchically Defined graphs\u201d, Journal of Algorithms, Vol. 8, 1987, pp. 260\u2013284.","journal-title":"Journal of Algorithms"},{"issue":"No.3","key":"3_CR13","doi-asserted-by":"crossref","first-page":"474","DOI":"10.1145\/65950.65952","volume":"36","author":"T. Lengauer","year":"1989","unstructured":"T. Lengauer, \u201cHierarchical Planarity Testing,\u201d J. ACM, Vol.36, No.3, July 1989, pp. 474\u2013509.","journal-title":"J. ACM"},{"key":"3_CR14","first-page":"63","volume":"44","author":"T. Lengauer","year":"1992","unstructured":"T. Lengauer, K.W. Wagner, \u201cThe correlation between the complexities of non-hierarchical and hierarchical versions of graph problems\u201d, JCSS, Vol. 44, 1992, pp. 63\u201393.","journal-title":"JCSS"},{"key":"3_CR15","unstructured":"P. Mirchandani and R.L. Francis, Discrete Location Theory, John Wiley and Sons, 1990."},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"M.V. Marathe, H.B. Hunt III, and S.S. Ravi, \u201cThe Complexity of Approximating PSPACE-Complete Problems for Hierarchical Specifications\u201d, in the proceedings of ICALP'93, July 1993, pp 76\u201387.","DOI":"10.1007\/3-540-56939-1_63"},{"key":"3_CR17","unstructured":"M.V. Marathe H.B. Hunt III and S.S. Ravi, \u201cGeometric Heuristics for Unit Disk Graphs\u201d, in the proceedings of 4th Canadian Conference on Computational Geometry, 1993, pp 244\u2013249."},{"key":"3_CR18","volume-title":"Operations Management","author":"J. O. McClain","year":"1992","unstructured":"J.O. McClain, L.J. Thomas and J.B. Mazzola, Operations Management, Prentice Hall, Englewood Cliffs, 1992."},{"key":"3_CR19","unstructured":"C. Mead and L. Conway, Introduction to VLSI systems Addison Wesley, 1980."},{"issue":"No.l","key":"3_CR20","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1137\/0213014","volume":"13","author":"N. Meggido","year":"1984","unstructured":"N. Meggido, K Supowit, \u201cOn The Complexity Of Some Common Geometric Location Problems,\u201d SIAM Journal Of Computing, Vol 13, No.l, February 1984, pp. 182\u2013196.","journal-title":"SIAM Journal Of Computing"},{"key":"3_CR21","doi-asserted-by":"crossref","unstructured":"K.W. Wagner, \u201cThe complexity of problems concerning graphs with regularities\u201d, Proc. 11th Symposium on Math. Foundations of Computer Science, LNCS 176, Springer-Verlag, 1984, pp. 544\u2013552.","DOI":"10.1007\/BFb0030338"},{"issue":"No.6","key":"3_CR22","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/0020-0190(88)90174-3","volume":"28","author":"D. W. Wang","year":"1988","unstructured":"D.W. Wang, Y.S. Kuo, \u201cA Study On Geometric Location Problems,\u201d Information Processing Letters, Vol.28, No.6, August 1988, pp. 281\u2013286.","journal-title":"Information Processing Letters"},{"key":"3_CR23","unstructured":"M. Williams, \u201cEfficient Processing of Hierarchical Graphs,\u201d TR 90-06, Dept of Computer Science, Iowa Sate University. (Parts of the report appeared in WADS'89 and SWAT'90 coauthored with Fernandez-Baca.)"},{"key":"3_CR24","volume-title":"Principles of Database and Knowledge Base Systems, Vol.1","author":"J. D. Ullman","year":"1988","unstructured":"J.D. Ullman, Principles of Database and Knowledge Base Systems, Vol.1, Computer Science Press, Rockville, MD, 1988."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57899-4_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,29]],"date-time":"2020-01-29T13:20:11Z","timestamp":1580304011000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57899-4_38"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540578994","9783540483854"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-57899-4_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]},"assertion":[{"value":"26 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}