{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T20:25:26Z","timestamp":1648671926528},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1997,1,1]],"date-time":"1997-01-01T00:00:00Z","timestamp":852076800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1997,1]]},"DOI":"10.1007\/bf02523239","type":"journal-article","created":{"date-parts":[[2006,11,7]],"date-time":"2006-11-07T23:39:46Z","timestamp":1162942786000},"page":"67-87","source":"Crossref","is-referenced-by-count":1,"title":["Parallel algorithms for the hamiltonian cycle and hamiltonian path problems in semicomplete bipartite digraphs"],"prefix":"10.1007","volume":"17","author":[{"given":"J.","family":"Bang-Jensen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"El Haddad","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Y.","family":"Manoussakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"T. M.","family":"Przytycka","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02523239_CR1","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0196-6774(89)90017-5","volume":"10","author":"K. Abrahamson","year":"1989","unstructured":"K. Abrahamson, N. Dadoun, D. G. Kirkpatrick, and T. Przytycka, A simple parallel tree contraction algorithm,J. Algorithms,10 (1989), 287\u2013302.","journal-title":"J. Algorithms"},{"key":"BF02523239_CR2","doi-asserted-by":"crossref","unstructured":"R. J. Anderson and G. L. Miller, Deterministic parallel list ranking,Proc. 3rd Egean Workshop on Computing, 1988, pp. 81\u201390.","DOI":"10.1007\/BFb0040376"},{"key":"BF02523239_CR3","doi-asserted-by":"crossref","first-page":"432","DOI":"10.1006\/jagm.1995.1045","volume":"19","author":"E. Bampis","year":"1995","unstructured":"E. Bampis, M. El Haddad, Y. Manoussakis, and M. Santha, A parallel reduction of hamilton cycle to hamilton path in tournaments,J. Algorithms,19 (1995), 432\u2013440.","journal-title":"J. Algorithms"},{"key":"BF02523239_CR4","unstructured":"J. Bang-Jensen, Arc-local tournament digraphs: a generalization of tournaments and bipartite tournaments, submitted."},{"key":"BF02523239_CR5","unstructured":"J. Bang-Jensen, G. Gutin, and J. Huang, A sufficient condition for a complete multipartite digraph to be hamiltonian,Discrete Math., to appear."},{"key":"BF02523239_CR6","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1137\/0403002","volume":"3","author":"A. Bar-Noy","year":"1990","unstructured":"A. Bar-Noy and J. Naor, Sorting, minimal feedback sets, and Hamiltonian paths in tournaments,SIAM J. Discrete Math.,3 (1990), 7\u201320.","journal-title":"SIAM J. Discrete Math."},{"key":"BF02523239_CR7","volume-title":"Selected Topics in Graph Theory 3","author":"L. W. Beineke","year":"1988","unstructured":"L. W. Beineke and R. J. Wilson,Selected Topics in Graph Theory 3, Academic Press, New York, 1988."},{"key":"BF02523239_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-349-03521-2","volume-title":"Graph Theory with Applications","author":"J. A. Bondy","year":"1976","unstructured":"J. A. Bondy and U. S. R. Murty,Graph Theory with Applications, MacMillan, New York, 1976."},{"key":"BF02523239_CR9","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/321812.321815","volume":"21","author":"R. P. Brent","year":"1974","unstructured":"R. P. Brent. The parallel evaluation of general arithmetic expressions,J. Assoc. Comput. Mach.,21 (1974), 201\u2013208.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02523239_CR10","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 J. Comput.,17 (1988), 770\u2013785.","journal-title":"SIAM J. Comput."},{"key":"BF02523239_CR11","doi-asserted-by":"crossref","unstructured":"R. Cole and U. Vishkin, Approximate and exact parallel scheduling with applications to list, tree and graph problems,Proc. 27th IEEE Symp. on Foundations of Computer Science, 1986, pp. 478\u2013491.","DOI":"10.1109\/SFCS.1986.10"},{"key":"BF02523239_CR12","doi-asserted-by":"crossref","unstructured":"D. Coppersmith and S. Winograd, Matrix multiplication via arithmetric progressions,Proc. 19th ACM Symp. on Theory of Computing, 1987, pp. 1\u20136.","DOI":"10.1145\/28395.28396"},{"key":"BF02523239_CR13","doi-asserted-by":"crossref","unstructured":"A. V. Goldberg, S. A. Plotkin, and P. M. Vaidya, Sublinear-time parallel algorithms for matching and related problems.Proc. 29th IEEE Symp. on Foundations of Computer Science, 1988, pp. 174\u2013185.","DOI":"10.21236\/ADA197411"},{"key":"BF02523239_CR14","first-page":"99","volume":"1","author":"G. Gutin","year":"1984","unstructured":"G. Gutin, A criterion for complete bipartite digraphs to be hamiltonian,Vests\u0129 Acad. Navuk BSSR Ser. F\u0129z.-Mat. Navuk, No. 1 (1984), 99\u2013100 (in Russian).","journal-title":"Vests\u0129 Acad. Navuk BSSR Ser. F\u0129z.-Mat. Navuk"},{"key":"BF02523239_CR15","first-page":"124","volume":"4","author":"G. Gutin","year":"1985","unstructured":"G. Gutin, Effective characterization of complete bipartite digraphs that have a hamiltonian path,Kibernetica, No. 4 (1985), 124\u2013125 (in Russian).","journal-title":"Kibernetica"},{"key":"BF02523239_CR16","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0196-6774(83)90011-1","volume":"4","author":"P. Hell","year":"1982","unstructured":"P. Hell and M. Rosenfeld, The complexity of finding generalized paths in tournaments,J. Algorithms,4 (1982), 303\u2013309.","journal-title":"J. Algorithms"},{"key":"BF02523239_CR17","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0020-0190(86)90141-9","volume":"22","author":"A. Israeli","year":"1986","unstructured":"A. Israeli and Y. Shiloach. An improved parallel algorithm for maximal matching,Inform. Process. Lett.,22 (1986), 57\u201360.","journal-title":"Inform. Process. Lett."},{"key":"BF02523239_CR18","first-page":"869","volume-title":"Handbook of Theoretical Computer Science","author":"R. M. Karp","year":"1990","unstructured":"R. M. Karp and V. Ramachandran, Parallel algorithms for shared-memory machines, inHandbook of Theoretical Computer Science, ed. J. Van. Leuwen, Elsevier, Amsterdam, 1990, pp. 869\u2013941."},{"key":"BF02523239_CR19","doi-asserted-by":"crossref","first-page":"830","DOI":"10.1145\/322217.322232","volume":"27","author":"R. E. Ladner","year":"1980","unstructured":"R. E. Ladner and M. J. Fisher, Parallel prefix sum computation.J. Assoc. Comput. Mach.,27 (1980), 830\u2013838.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02523239_CR20","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0166-218X(92)90233-Z","volume":"36","author":"Y. Manoussakis","year":"1992","unstructured":"Y. Manoussakis, A linear-time algorithm for finding hamiltonian cycles in tournaments,Discrete Appl. Math.,36 (1992), 199\u2013201.","journal-title":"Discrete Appl. Math."},{"key":"BF02523239_CR21","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1137\/0217044","volume":"17","author":"G. L. Miller","year":"1988","unstructured":"G. L. Miller, V. Ramachandran, and E. Kaltofen, Efficient parallel evaluation of straight line code and arithmetic circuits,SIAM J. Comput.,17 (1988), 687\u2013695.","journal-title":"SIAM J. Comput."},{"key":"BF02523239_CR22","doi-asserted-by":"crossref","unstructured":"G. L. Miller and J. Reif, Parallel tree contraction and its application,Proc. 26th IEEE Symp. on Foundations of Computer Science, 1985, pp. 478\u2013489.","DOI":"10.1109\/SFCS.1985.43"},{"key":"BF02523239_CR23","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K. Mulmuley","year":"1987","unstructured":"K. Mulmuley, U. V. Vazirani, and V. B. Vazirani, Matching is as easy as matrix inversion,Combinatorica,7 (1987), 105\u2013113.","journal-title":"Combinatorica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02523239.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02523239\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02523239","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T16:39:41Z","timestamp":1558283981000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02523239"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,1]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1997,1]]}},"alternative-id":["BF02523239"],"URL":"https:\/\/doi.org\/10.1007\/bf02523239","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,1]]}}}