{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:54:57Z","timestamp":1725663297113},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540515425"},{"type":"electronic","value":"9783540482376"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-51542-9_26","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:06:50Z","timestamp":1330204010000},"page":"303-315","source":"Crossref","is-referenced-by-count":0,"title":["Parallel algorithms for the subgraph homeomorphism problem"],"prefix":"10.1007","author":[{"given":"Samir","family":"Khuller","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"key":"26_CR1","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, \u2018An approach to the subgraph homeomorphism problem', Theoretical Computer Science, 38 (1985), pp. 249\u2013267.","journal-title":"Theoretical Computer Science"},{"key":"26_CR2","volume-title":"Graph Theory with applications","author":"J. A. Bondy","year":"1977","unstructured":"J.A. Bondy and U.S.R. Murty, \u2018Graph Theory with applications,\u2019 American Elsevier, New York (1977)."},{"key":"26_CR3","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.E. Hopcroft and J. Wyllie, \u2018The directed subgraph homeomorphism problem', Theoretical Computer Science, 10 (1980), pp. 111\u2013121.","journal-title":"Theoretical Computer Science"},{"key":"26_CR4","first-page":"149","volume":"319","author":"D. Fussel","year":"1988","unstructured":"D. Fussel and R. Thurimella, \u2018Separation pair detection', Proceedings of AWOC 88, LNCS 319, (1988), pp. 149\u2013159.","journal-title":"Proceedings of AWOC 88, LNCS"},{"key":"26_CR5","unstructured":"M.R.Garey and D.S.Johnson, \u2018Computers and Intractability: A guide to the theory of NP-completeness', Freeman, San Francisco."},{"key":"26_CR6","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1090\/S0002-9904-1943-08065-2","volume":"49","author":"D. W. Hall","year":"1943","unstructured":"D.W. Hall, \u2018A note on primitive skew curves', Bull. Amer. Math. Soc., 49 (1943), pp. 935\u2013937.","journal-title":"Bull. Amer. Math. Soc."},{"key":"26_CR7","doi-asserted-by":"crossref","unstructured":"S.Khuller, S.G.Mitchell, V.V.Vazirani, \u2018NC Algorithms for the two disjoint paths problem and for finding a Kuratowski homeomorph', Technical Report TR 88-960, Computer Science Department, Cornell University, (1988).","DOI":"10.1109\/SFCS.1989.63494"},{"key":"26_CR8","doi-asserted-by":"crossref","unstructured":"P.N.Klein and J.H.Reif, \u2018An efficient parallel algorithm for planarity', Proceedings of FOCS conference, (1986), pp. 465\u2013477.","DOI":"10.1109\/SFCS.1986.6"},{"key":"26_CR9","unstructured":"S.Khuller and B.Schieber, \u2018Efficient parallel algorithms for testing connectivity and finding disjoint s-t paths', in preparation."},{"key":"26_CR10","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0022-0000(80)90057-4","volume":"20","author":"A. S. LaPaugh","year":"1980","unstructured":"A.S. LaPaugh and R.L. Rivest, \u2018The subgraph homeomorphism problem', Journal of Computer and System Sciences, 20, (1980), pp. 133\u2013149.","journal-title":"Journal of Computer and System Sciences"},{"key":"26_CR11","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0304-3975(86)90153-2","volume":"47","author":"Y. Maon","year":"1986","unstructured":"Y. Maon, B. Schieber and U. Vishkin, \u2018Parallel ear decomposition search (EDS) and st-numbering in graphs', Theoretical Computer Science, 47 (1986), pp. 277\u2013298.","journal-title":"Theoretical Computer Science"},{"key":"26_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/322047.322048","volume":"25","author":"Y. Perl","year":"1978","unstructured":"Y. Perl and Y. Shiloach, \u2018Finding two disjoint paths between two pairs of vertices in a graph', Journal of the Association for Computing Machinery, 25, (1978), pp. 1\u20139.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"26_CR13","unstructured":"N.Robertson and P.D.Seymour, \u2018The disjoint paths problem', manuscript, (1986)."},{"key":"26_CR14","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1145\/322203.322207","volume":"27","author":"Y. Shiloach","year":"1980","unstructured":"Y. Shiloach, \u2018A polynomial solution to the undirected two path problem', Journal of the Association for Computing Machinery, 27, (1980), pp. 445\u2013456.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"26_CR15","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0196-6774(82)90008-6","volume":"3","author":"Y. Shiloach","year":"1982","unstructured":"Y. Shiloach and U. Vishkin, \u2018An O(log n) parallel connectivity algorithm', Journal of Algorithms, vol.3, (1982), pp 57\u201363.","journal-title":"Journal of Algorithms"},{"key":"26_CR16","doi-asserted-by":"crossref","first-page":"862","DOI":"10.1137\/0214061","volume":"14","author":"R. E. Tarjan","year":"1985","unstructured":"R.E. Tarjan and U. Vishkin, \u2018An efficient parallel biconnectivity algorithm', SIAM Journal on Computing, 14 (1985), pp. 862\u2013874.","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"26_CR17","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1016\/0890-5401(89)90017-5","volume":"80","author":"V. V. Vazirani","year":"1989","unstructured":"V.V. Vazirani, \u2018NC Algorithms for computing the number of perfect matchings in K 3,3-free graphs and related problems', Information and Computation 80, No. 2 (1989), pp. 152\u2013164.","journal-title":"Information and Computation"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51542-9_26.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:21:54Z","timestamp":1605648114000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51542-9_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540515425","9783540482376"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-51542-9_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]}}}