{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:53:04Z","timestamp":1725663184020},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540186250"},{"type":"electronic","value":"9783540480334"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1987]]},"DOI":"10.1007\/3-540-18625-5_44","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T14:41:27Z","timestamp":1330180887000},"page":"79-94","source":"Crossref","is-referenced-by-count":1,"title":["Fast parallel algorithms for the subgraph homeomorphism and the subgraph isomorphism problem for classes of planar graphs"],"prefix":"10.1007","author":[{"given":"Andrzej","family":"Lingas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Proskurowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,27]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"A. Aggarwal, B. Chazelle, L. Guibas, C. O'Dunlaing, and C. Yap, Parallel Computational Geometry, in Proc. 25th Annual IEEE Symposium on Foundations of Computer Science 1985, 468\u2013477.","DOI":"10.1109\/SFCS.1985.42"},{"key":"8_CR2","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"A.V. Aho, J.E. Hopcroft and J.D. Ullman, The Design and Analysis of Computer Algorithms, (Addison-Wesley, Reading, Massachusetts, 1974)."},{"issue":"2","key":"8_CR3","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0607033","volume":"7","author":"S. Arnborg","year":"1986","unstructured":"S. Arnborg and A. Proskurowski, Characterization and recognition of partial 3-trees, SIAM Journal of Algebraic and Discrete Methods 7, 2(1986), 305\u2013314.","journal-title":"SIAM Journal of Algebraic and Discrete Methods"},{"key":"8_CR4","unstructured":"S. Arnborg, A. Proskurowski, and D.G. Corneil, Forbidden minors characterization of partial 3-trees, UO-CIS-TR-86-07, University of Oregon (1986)"},{"key":"8_CR5","volume-title":"Parallel Sorting Algorithms","author":"S. G. Akl","year":"1985","unstructured":"S.G. Akl, Parallel Sorting Algorithms, (Academic Press, New York, 1985)."},{"key":"8_CR6","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0304-3975(85)90222-1","volume":"38","author":"T. Asano","year":"1985","unstructured":"T. Asano, An approach to the subgraph homeomorphism problem, Theoretical Computer Science, 38 (1985), 249\u2013267.","journal-title":"Theoretical Computer Science"},{"key":"8_CR7","doi-asserted-by":"crossref","unstructured":"S.A. Cook, The Classification of Problems which have Fast Parallel Algorithm, in Proc. Foundations of Computation Theory, Borgholm, Sweden 1983, Springer-Verlag LNCS 158.","DOI":"10.1007\/3-540-12689-9_95"},{"key":"8_CR8","first-page":"433","volume":"3","author":"G. Chartrand","year":"1967","unstructured":"G. Chartrand and F. Harary, Planar permutation graphs, Ann. Inst. Henri Poincar\u00e9 Sec. B 3(1967), 433\u2013438.","journal-title":"Ann. Inst. Henri Poincar\u00e9 Sec. B"},{"key":"8_CR9","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S. Fortune","year":"1980","unstructured":"S. Fortune, J. Hopcroft, and J. Wyllie, The directed subgraph homeomorphism problem, Theoretical Computer Science 10 (1980), 111\u2013121.","journal-title":"Theoretical Computer Science"},{"key":"8_CR10","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, 1979)."},{"key":"8_CR11","doi-asserted-by":"crossref","DOI":"10.21236\/AD0705364","volume-title":"Graph Theory","author":"F. Harary","year":"1969","unstructured":"F. Harary, Graph Theory (Addison-Wesley, Reading Massachusetts, 1969)."},{"key":"8_CR12","doi-asserted-by":"crossref","unstructured":"A. Lingas, On partitioning polygons, in Proc. of 1st ACM Symposium on Computational Geometry, Baltimore 1985.","DOI":"10.1145\/323233.323270"},{"key":"8_CR13","doi-asserted-by":"crossref","unstructured":"A. Lingas, Subgraph Isomorphism for Biconnected Outerplanar Graphs in Cubic Time, in Proc. 3rd STACS, Orsay 1986, Springer-Verlag, LNCS 210.","DOI":"10.1007\/3-540-16078-7_68"},{"key":"8_CR14","unstructured":"A. Lingas, M. Karpinski, Subtree isomorphism and bipartite perfect matching are mutually NC reducible, manuscript (1986)."},{"issue":"3","key":"8_CR15","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1137\/0209046","volume":"9","author":"R. J. Lipton","year":"1980","unstructured":"R.J. Lipton and R.E. Tarjan, Applications of a planar separator theorem, SIAM J. Computing 9, 3(1980), 513\u2013524.","journal-title":"SIAM J. Computing"},{"key":"8_CR16","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/S0167-5060(08)70324-8","volume":"2","author":"D. W. Matula","year":"1978","unstructured":"D.W. Matula, Subtree isomorphism in O(n 2 s ), Annals of Discrete Mathematics 2 (1978), 91\u2013406.","journal-title":"Annals of Discrete Mathematics"},{"issue":"5","key":"8_CR17","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/0020-0190(79)90075-9","volume":"9","author":"S. L. Mitchell","year":"1979","unstructured":"S.L. Mitchell, Linear algorithms to recognize outerplanar and maximal outerplanar graphs, Information Processing Letters 9, 5(1979), 229\u2013232.","journal-title":"Information Processing Letters"},{"key":"8_CR18","doi-asserted-by":"crossref","unstructured":"G. Miller and J.H. Reif, Parallel Tree Contraction and its Applications, in Proc. 26th Annual IEEE Symposium on Foundations of Computer Science 1985, 478\u2013489.","DOI":"10.1109\/SFCS.1985.43"},{"issue":"2","key":"8_CR19","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1137\/0606030","volume":"6","author":"N. Robertson","year":"1985","unstructured":"N. Robertson and P.D. Seymour, Disjoint paths \u2014 a survey, SIAM J. Alg. Disc. Meth., Vol. 6 (1985), No. 2, 300\u2013305.","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"8_CR20","doi-asserted-by":"crossref","unstructured":"N. Robertson and P.D. Seymour, Graph minors \u2014 a survey, submitted for publication (1986).","DOI":"10.1017\/CBO9781107325678.009"},{"key":"8_CR21","doi-asserted-by":"crossref","unstructured":"N. Pippenger, On simultaneous resource bounds, in Proc. 20th Annual IEEE Symposium on Foundations of Computer Science 1979, 307\u2013311.","DOI":"10.1109\/SFCS.1979.29"},{"key":"8_CR22","unstructured":"F.P. Preparata and M.I. Shamos, Computational Geometry, An Introduction, Texts and Monographs in Computer Science, Springer-Verlag, New York."},{"key":"8_CR23","unstructured":"K.R. Reischuk, Parallel Machines and their Communication Theoretical Limits, in Proc. 3rd STACS, Orsay 1986, Springer-Verlag, LNCS 210."},{"issue":"3","key":"8_CR24","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1145\/2514.2515","volume":"16","author":"M. J. Quinn","year":"1984","unstructured":"M.J. Quinn and N. Deo, Parallel Graph Algorithms, Computing Surveys, Vol. 16, No. 3 (1984), 320\u2013348.","journal-title":"Computing Surveys"},{"key":"8_CR25","doi-asserted-by":"publisher","first-page":"730","DOI":"10.1137\/0206053","volume":"6","author":"S. W. Reyner","year":"1977","unstructured":"S.W. Reyner, An analysis of a good algorithm for the subtree problem, SIAM J. Computing 6 (1977), 730\u2013732.","journal-title":"SIAM J. Computing"},{"key":"8_CR26","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","volume":"22","author":"W. L. Ruzzo","year":"1981","unstructured":"W.L. Ruzzo, On uniform circuit complexity, J. Computer and System Science 22 (1981), 365\u2013383.","journal-title":"J. Computer and System Science"},{"key":"8_CR27","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1137\/0213027","volume":"13","author":"L. Stockmeyer","year":"1984","unstructured":"L. Stockmeyer and U. Vishkin, Simulation of Parallel Random Access Machines by Circuits, SIAM J. Computing 13 (1984), 409\u2013422.","journal-title":"SIAM J. Computing"},{"key":"8_CR28","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/0304-3975(82)90133-5","volume":"17","author":"M. M. Syslo","year":"1982","unstructured":"M.M. Syslo, The subgraph isomorphism problem for outerplanar graphs, Theoretical Computer Science 17 (1982), 91\u201397.","journal-title":"Theoretical Computer Science"},{"key":"8_CR29","unstructured":"M.M.Syslo, private communication."},{"key":"8_CR30","doi-asserted-by":"crossref","unstructured":"R.E. Tarjan and U. Vishkin, Finding Bi-connected Components and Computing Tree Functions in Logarithmic Parallel Time, in Proc. 25th Annual IEEE Symposium on Foundations of Computer Science 1984, 12\u201320.","DOI":"10.1109\/SFCS.1984.715896"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-18625-5_44.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,30]],"date-time":"2021-12-30T21:14:04Z","timestamp":1640898844000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-18625-5_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987]]},"ISBN":["9783540186250","9783540480334"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/3-540-18625-5_44","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1987]]}}}