{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:10:48Z","timestamp":1725664248199},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540580782"},{"type":"electronic","value":"9783540484356"}],"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-58078-6_5","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T15:10:44Z","timestamp":1330269044000},"page":"45-57","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["NC2 Algorithms regarding Hamiltonian paths and circuits in interval graphs"],"prefix":"10.1007","author":[{"given":"Y. Daniel","family":"Liang","sequence":"first","affiliation":[]},{"given":"Raymond","family":"Greenlaw","sequence":"additional","affiliation":[]},{"given":"Glenn","family":"Manacher","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"issue":"6","key":"5_CR1","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/0020-0190(90)90209-G","volume":"33","author":"A. A. Bertossi","year":"1990","unstructured":"A. A. Bertossi and S. Moretti. Parallel algorithms on circular-arc graphs. Information Processing Letters 33(6) (1990) 275\u2013281.","journal-title":"Information Processing Letters"},{"key":"5_CR2","doi-asserted-by":"crossref","unstructured":"M. S. Chang, S. L. Pang, and J. L. Liaw. Deferred-query \u2014 an efficient approach for some problems on interval graphs. Manuscript, 1993.","DOI":"10.1007\/3-540-57155-8_250"},{"issue":"4","key":"5_CR3","doi-asserted-by":"crossref","first-page":"770","DOI":"10.1137\/0217049","volume":"17","author":"R. Cole","year":"1988","unstructured":"R. Cole. Parallel merge sort. SIAM Journal on Computing 17(4) (1988) 770\u2013785.","journal-title":"SIAM Journal on Computing"},{"key":"5_CR4","unstructured":"E. Dekel and S. Sahni. A parallel algorithm for convex bipartite graphs. Proceedings International Conference on Parallel Processing (1982) 178\u2013184."},{"key":"5_CR5","first-page":"843","volume-title":"Synthesis of Parallel Algorithms","author":"F. E. Fich","year":"1993","unstructured":"Faith E. Fich. The complexity of computation on the parallel random access machine. In Reif [18], chapter 20, pages 843\u2013899."},{"key":"5_CR6","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, San Francisco, 1979."},{"key":"5_CR7","doi-asserted-by":"crossref","first-page":"539","DOI":"10.4153\/CJM-1964-055-5","volume":"16","author":"P. C. Gilmore","year":"1964","unstructured":"P. C. Gilmore and A. J. Hoffman. A characterization of comparability graphs and of interval graphs. Canadian Journal of Mathematics 16 (1964) 539\u2013548.","journal-title":"Canadian Journal of Mathematics"},{"key":"5_CR8","unstructured":"R. Greenlaw, H. J. Hoover, and W. L. Ruzzo.Topics in Parallel Computation: A Guide to the Theory of P-completeness. Oxford University Press, New York, to appear."},{"issue":"6","key":"5_CR9","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/0020-0190(88)90178-0","volume":"28","author":"C-W. Ho","year":"1988","unstructured":"C-W. Ho and R. C. T. Lee. Efficient parallel algorithms for finding maximum cliques, clique trees, and minimum coloring on chordal graphs. Information Processing Letters 28(6) (1988) 301\u2013309.","journal-title":"Information Processing Letters"},{"key":"5_CR10","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R. M. Karp","year":"1972","unstructured":"R. M. Karp. Reducibility among combinatorial problems, in R. E. Miller and J. W. Thatcher, eds., Complexity of Computer Computations, Plenum Press, New York, (1972) 85\u2013103."},{"key":"5_CR11","doi-asserted-by":"crossref","unstructured":"R. M. Karp and V. Ramachandran. Parallel algorithms for shared-memory machines. In van Leeuwan [19], chapter 17, pages 869\u2013941.","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"issue":"4","key":"5_CR12","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/0020-0190(85)90050-X","volume":"20","author":"J. M. Keil","year":"1985","unstructured":"J. M. Keil. Finding Hamiltonian circuit in interval graphs. Information Processing Letters 20(4) (1985) 201\u2013206.","journal-title":"Information Processing Letters"},{"key":"5_CR13","doi-asserted-by":"crossref","unstructured":"Y. D. Liang, R. Greenlaw, and G. K. Manacher. NC 2 Algorithms Regarding Hamiltonian Paths and Circuits in Interval Graphs. Technical report 93-11, University of New Hampshire, 1993.","DOI":"10.1007\/3-540-58078-6_5"},{"key":"5_CR14","doi-asserted-by":"crossref","unstructured":"Y. D. Liang, G. K. Manacher, C. Rhee, and T. A. Mankus. An O(n log n) algorithm for finding Hamiltonian paths and circuits in circular-arc graphs. Manuscript, August, 1992.","DOI":"10.1145\/170791.170879"},{"issue":"4","key":"5_CR15","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/BF00264533","volume":"15","author":"W. Lipski Jr.","year":"1981","unstructured":"W. Lipski Jr. and F. P. Preparata. Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems. Acta Informatica 15(4) (1981) 329\u2013346.","journal-title":"Acta Informatica"},{"issue":"4","key":"5_CR16","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0020-0190(90)90025-S","volume":"35","author":"G. K. Manacher","year":"1990","unstructured":"G. K. Manacher, T. A. Mankus, and A. J. Smith. An optimum O(n log n) algorithm for finding a canonical Hamiltonian circuit in a set of intervals. Information Processing Letters 35(4) (1990) 205\u2013211.","journal-title":"Information Processing Letters"},{"key":"5_CR17","doi-asserted-by":"crossref","unstructured":"J. Naor, M. Naor, and A. A. Sch\u00e4ffer. Fast parallel algorithms for chordal graphs. Proceedings 19th Ann. ACM Symposium on Theory of Computing (1987) 355\u2013364.","DOI":"10.1145\/28395.28433"},{"volume-title":"Synthesis of Parallel Algorithms","year":"1993","key":"5_CR18","unstructured":"John H. Reif, editor. Synthesis of Parallel Algorithms. Morgan Kaufman, San Mateo, CA, 1993."},{"key":"5_CR19","unstructured":"Jan van Leeuwan, editor. Handbook of Theoretical Computer Science, volume A: Algorithms and Complexity. M.I.T. Press\/Elsevier, 1990."}],"container-title":["Lecture Notes in Computer Science","Parallel and Distributed Computing Theory and Practice"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58078-6_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,31]],"date-time":"2021-12-31T05:58:57Z","timestamp":1640930337000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58078-6_5"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540580782","9783540484356"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-58078-6_5","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":"1 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}