{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:08:28Z","timestamp":1725455308047},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540605737"},{"type":"electronic","value":"9783540477662"}],"license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"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":[[1995]]},"DOI":"10.1007\/bfb0015416","type":"book-chapter","created":{"date-parts":[[2005,11,13]],"date-time":"2005-11-13T01:50:06Z","timestamp":1131846606000},"page":"132-141","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The parallel complexity of approximating the High Degree Subgraph problem"],"prefix":"10.1007","author":[{"given":"A. E.","family":"Andreev","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Clementi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P.","family":"Crescenzi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"E.","family":"Dahlhaus","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"de Agostino","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. D. P.","family":"Rolim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,9]]},"reference":[{"unstructured":"N. Alon and J.H. Spencer (1992), The Probabilistic Method, Wiley-Interscience Publication.","key":"15_CR1"},{"unstructured":"R. Anderson, and E.W. Mayr (1984), \u201cA P-complete problem and approximation to it\u201d, Technical Report STAN-CS-84-1014, Department of Computer Science, Stanford University.","key":"15_CR2"},{"unstructured":"R. Anderson, and E.W. Mayr (1987), \u201cParallelism and greedy algorithms\u201d, in Advances in Computing Research: Parallel and Distributed Computing, F.P. Preparata (ed.), JAI Press, 17\u201338.","key":"15_CR3"},{"unstructured":"B. Bollobas (1985), Random Graphs, Academic Press.","key":"15_CR4"},{"doi-asserted-by":"crossref","unstructured":"G. Bongiovanni, P. Crescenzi, S. De Agostino (1995), \u201cMAX SAT and MIN SET COVER Approximation Algorithms are P-Complete\u201d, Parallel Processing Letters, to appear.","key":"15_CR5","DOI":"10.1142\/S0129626495000278"},{"unstructured":"D.P. Bovet, A. Clementi, P. Crescenzi, R. Silvestri (1995), \u201cParallel approximation algorithms for optimization problems\u201d, Technical Report SI\/R.R-95\/09. Department of Computer Science, Rome University.","key":"15_CR6"},{"doi-asserted-by":"crossref","unstructured":"A. Clementi, J. Rolim, L. Kucera (1994), \u201cA Note on Parallel Randomized Algorithms for Searching Problems\u201d. DIMACS Series in Discrete Mathematics and Theoretical Computer Sciences, American Mathematical Society, to appear.","key":"15_CR7","DOI":"10.1090\/dimacs\/022\/02"},{"key":"15_CR8","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1007\/BF02759702","volume":"1","author":"P. Erdos","year":"1963","unstructured":"P. Erdos (1963), \u201cOn the structure of linear graphs\u201d. Israel Journal of Mathematics 1, 156\u2013160.","journal-title":"Israel Journal of Mathematics"},{"key":"15_CR9","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/0022-0000(89)90026-3","volume":"39","author":"R. Greenlaw","year":"1989","unstructured":"R. Greenlaw (1989), \u201cOrdered vertex removal and subgraph problems\u201d, J. Comput. System Sci. 39, 323\u2013342.","journal-title":"J. Comput. System Sci."},{"key":"15_CR10","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0890-5401(92)90033-C","volume":"97","author":"R. Greenlaw","year":"1992","unstructured":"R. Greenlaw (1992), \u201cA model classifying algorithms as inherently sequential with applications to graph searching\u201d, Information and Computation 97, 133\u2013149.","journal-title":"Information and Computation"},{"doi-asserted-by":"crossref","unstructured":"R. Greenlaw. H.J. Hoover, and W.L. Ruzzo (1995). Limits to parallel computation: P-completeness theory, Oxford University Press, to appear.","key":"15_CR11","DOI":"10.1093\/oso\/9780195085914.001.0001"},{"doi-asserted-by":"crossref","unstructured":"R.M. Karp and V. Ramachandran (1990), \u201cParallel algorithms for shared memory machines\u201d, in Handbook of Theoretical Computer Science, J. van Leeuwen (ed.), MIT Press\/Elsevier, Vol. A, 869\u2013941.","key":"15_CR12","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"unstructured":"D. Kavvadias. G.E. Pantziou, P.G. Spirakis, C. D. Zaroliagis (1994), \u201cHammock-on-Ears Decomposition: A Technique for the Efficient Parallel Solution of Shortest Paths and Other Problems\u201d, Proc. of the 19th MFCS, LNCS, 462\u2013472.","key":"15_CR13"},{"unstructured":"L.M. Kirousis. M.J. Serna, P. Spirakis (1989), \u201cThe parallel complexity of the connected subgraph problem\u201d, Proc. 30th IEEE-FOCS, 446\u2013456.","key":"15_CR14"},{"key":"15_CR15","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/990518.990519","volume":"7","author":"R.E. Ladner","year":"1975","unstructured":"R.E. Ladner (1975), \u201cThe circuit value problem is log-space complete for P\u201d SIGACT News 7, 18\u201321.","journal-title":"SIGACT News"},{"doi-asserted-by":"crossref","unstructured":"S. Nikoletseas, K. Palem, P. Spirakis. M. Yung (1994). \u201cShort Vertex Disjoint paths and Multiconnectivity in Random Graphs: Reliable Networks Computing\u201d, Proc. of the 21st ICALP, LNCS, 508\u2013519.","key":"15_CR16","DOI":"10.1007\/3-540-58201-0_94"},{"unstructured":"K. Wagner (1970), Graphentheorie, Bibliographische Inst. AG.","key":"15_CR17"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computations"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0015416","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,19]],"date-time":"2021-07-19T12:18:23Z","timestamp":1626697103000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0015416"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540605737","9783540477662"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/bfb0015416","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]},"assertion":[{"value":"9 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}