{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T11:33:45Z","timestamp":1742988825358,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540569398"},{"type":"electronic","value":"9783540478263"}],"license":[{"start":{"date-parts":[[1993,1,1]],"date-time":"1993-01-01T00:00:00Z","timestamp":725846400000},"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":[[1993]]},"DOI":"10.1007\/3-540-56939-1_63","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T06:57:03Z","timestamp":1330239423000},"page":"76-87","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["The complexity of approximating PSPACE-complete problems for hierarchical specifications"],"prefix":"10.1007","author":[{"given":"M. V.","family":"Marathe","sequence":"first","affiliation":[]},{"suffix":"III","given":"H. B.","family":"Hunt","sequence":"additional","affiliation":[]},{"given":"S. S.","family":"Ravi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,28]]},"reference":[{"key":"7_CR1","unstructured":"R.J. Anderson and E.W. Mayr \u201cApproximating P-complete problems,\u201d Tech Report, Stanford University, 1986."},{"key":"7_CR2","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":"7_CR3","doi-asserted-by":"crossref","unstructured":"A. Condon, J. Feigenbaum, C. Lund and P. Shor, \u201cProbabilistically Checkable Debate Systems and Approximation Algorithms for PSPACE-Hard Functions\u201d, to appear in Proc. 25th ACM Symposium on Theory of Computing, 1993.","DOI":"10.1145\/167088.167190"},{"key":"7_CR4","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":"7_CR5","volume-title":"Computers and Intractability. A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M.R. Garey, D.S. Johnson, Computers and Intractability. A Guide to the Theory of NP-Completeness, Freeman, San Francisco CA, 1979."},{"key":"7_CR6","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":"7_CR7","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.4","key":"7_CR8","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1145\/4221.4226","volume":"32","author":"R. M. Karp","year":"1985","unstructured":"R.M. Karp, A. Wigderson, \u201cA Fast Parallel Algorithm for the Maximal Independent Set Problem\u201d, J.ACM, Vol. 32, No.4, July 1985, pp. 762\u2013773.","journal-title":"J.ACM"},{"key":"7_CR9","doi-asserted-by":"crossref","unstructured":"L. Kirousis, M. Serna and P. Spirakis, \u201cThe Parallel Complexity of the Subgraph Connectivity problem,\u201d Proc. 30th IEEE-FOCS, 1989, pp. 294\u2013299","DOI":"10.1109\/SFCS.1989.63493"},{"key":"7_CR10","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF02310101","volume":"39","author":"T. Lengauer","year":"1987","unstructured":"T. Lengauer and C. Weiner, \u201cEfficient Solutions hierarchical systems of linear equations,\u201d Computing, Vol 39, 1987, pp. 111\u2013132.","journal-title":"Computing"},{"key":"7_CR11","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"},{"issue":"No.3","key":"7_CR12","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"},{"issue":"No.6","key":"7_CR13","doi-asserted-by":"crossref","first-page":"1063","DOI":"10.1137\/0217068","volume":"17","author":"T. Lengauer","year":"1988","unstructured":"T. Lengauer, \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":"7_CR14","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"},{"key":"7_CR15","doi-asserted-by":"crossref","unstructured":"T. Lengauer, \u201cExploiting Hierarchy in VLSI Design,\u201d Proc. AWOC '86, LNCS 227, Springer-Verlag, 1986, pp. 180\u2013193.","DOI":"10.1007\/3-540-16766-8_16"},{"issue":"No.4","key":"7_CR16","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0020-0190(91)90194-M","volume":"37","author":"M. Serna","year":"1991","unstructured":"M. Serna, \u201cApproximating Linear Programming is log-space complete for P,\u201d Inf. Proc. Letters, Vol. 37, No. 4, 1991, pp. 233\u2013236.","journal-title":"Inf. Proc. Letters"},{"key":"7_CR17","doi-asserted-by":"crossref","unstructured":"G. Pantziou, P. Spirakis, C. Zaroliagis, \u201cFast Parallel Approximations of the Maximum Weighted Cut Problem Through Derandomization,\u201d Proc. 9\n\n                  th\n                \nFoundations of Software Technology and Theoretical Computer Science, FCT-TCS, 1989, pp. 20\u201329.","DOI":"10.1007\/3-540-52048-1_29"},{"issue":"No.3","key":"7_CR18","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF00289117","volume":"23","author":"K. W. Wagner","year":"1986","unstructured":"K.W. Wagner, \u201cThe complexity of Combinatorial Problems with Succinct Input Representation,\u201d Acta Informatica, Vol. 23, No.3, 1986, pp. 325\u2013356.","journal-title":"Acta Informatica"},{"key":"7_CR19","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 F. Baca.)"},{"key":"7_CR20","unstructured":"M. Yannakakis, \u201cOn the Approximation of Maximum Satisfiability,\u201d Proc. Third Annual ACM-SIAM Symp. on Discrete Algorithms, Jan. 1992, pp 1\u20139."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56939-1_63","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,29]],"date-time":"2020-01-29T09:07:20Z","timestamp":1580288840000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56939-1_63"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540569398","9783540478263"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-56939-1_63","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]},"assertion":[{"value":"28 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}