{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:56:48Z","timestamp":1725663408349},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540542339"},{"type":"electronic","value":"9783540475163"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54233-7_153","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T22:38:21Z","timestamp":1330209501000},"page":"429-440","source":"Crossref","is-referenced-by-count":0,"title":["An efficient NC algorithm for finding Hamiltonian cycles in dense directed graphs"],"prefix":"10.1007","author":[{"given":"Martin","family":"F\u00fcrer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Balaji","family":"Raghavachari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"33_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02122548","volume":"8","author":"A. Aggarwal","year":"1988","unstructured":"A. Aggarwal and R.J. Anderson, A Random NC-algorithm for Depth First Search, Combinatorica 8 (1988) 1\u201312.","journal-title":"Combinatorica"},{"key":"33_CR2","doi-asserted-by":"crossref","unstructured":"A. Aggarwal, R.J. Anderson and M. Kao, Parallel Depth-First Search in General Directed Graphs, Proc. 21st ACM STOC (1989) 297\u2013308.","DOI":"10.1145\/73007.73035"},{"key":"33_CR3","unstructured":"S.G. Akl, The Design and Analysis of Parallel Algorithms, Prentice-Hall, 1989."},{"key":"33_CR4","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/BF02579320","volume":"7","author":"R.J. Anderson","year":"1987","unstructured":"R.J. Anderson, A Parallel Algorithm for the Maximal Path Problem, Combinatorica 7 (1987) 315\u2013326.","journal-title":"Combinatorica"},{"key":"33_CR5","doi-asserted-by":"crossref","unstructured":"A. Awerbuch, A. Israeli and Y. Shiloach, Finding Euler Circuits in Logarithmic Parallel Time, Proc. 16th ACM STOC (1984) 249\u2013257.","DOI":"10.1145\/800057.808688"},{"key":"33_CR6","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, American Elsevier, New York 1976."},{"key":"33_CR7","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/0196-6774(89)90012-6","volume":"10","author":"N. Chiba","year":"1989","unstructured":"N. Chiba and T. Nishizeki, The Hamiltonian Cycle Problem is Linear-Time Solvable for Four-connected Planar Graphs, J. Algorithms 10 (1989) 187\u2013211.","journal-title":"J. Algorithms"},{"key":"33_CR8","doi-asserted-by":"crossref","unstructured":"E. Dahlhaus, P. Hajnal and M. Karpinski, Optimal Parallel Algorithm for the Hamiltonian Cycle Problem on Dense Graphs, 29th Annual Symp. on Foundations of Comp. Sci. (1988) 186\u2013193.","DOI":"10.1109\/SFCS.1988.21936"},{"key":"33_CR9","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1112\/plms\/s3-2.1.69","volume":"2","author":"G.A. Dirac","year":"1952","unstructured":"G.A. Dirac, Some Theorems on Abstract Graphs, Proc. Lond. Math. Soc. 2 (1952), 69\u201381.","journal-title":"Proc. Lond. Math. Soc."},{"key":"33_CR10","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0020-0190(87)90229-8","volume":"25","author":"A.M. Frieze","year":"1987","unstructured":"A.M. Frieze, Parallel Algorithms for Finding Hamiltonian Cycles in Random Graphs, Inf. Proc. Lett. 25 (1987) 111\u2013117.","journal-title":"Inf. Proc. Lett."},{"key":"33_CR11","unstructured":"M. F\u00fcrer and B. Raghavachari, An efficient NC approximation algorithm for edgecoloring graphs with applications to maximal matching, In preparation."},{"key":"33_CR12","unstructured":"M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, W.H. Freeman, 1979."},{"key":"33_CR13","unstructured":"M. Gondran and M. Minoux, Graphs and Algorithms, John Wiley & Sons, 1979."},{"key":"33_CR14","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, Inf. Proc. Lett. 22 (1986) 57\u201360.","journal-title":"Inf. Proc. Lett."},{"key":"33_CR15","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0095-8956(80)90042-8","volume":"29","author":"B. Jackson","year":"1980","unstructured":"B. Jackson, Hamilton Cycles in Regular 2-Connected Graphs, J. Comb. Theory Ser. B 29 (1980) 27\u201346.","journal-title":"J. Comb. Theory Ser. B"},{"key":"33_CR16","doi-asserted-by":"crossref","unstructured":"R.M. Karp and V.L. Ramachandran, A Survey of Parallel Algorithms for Shared Memory Machines, Handbook of Theoretical Computer Science, edited by J. van Leeuwen, MIT Press, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50022-9"},{"key":"33_CR17","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0020-0190(89)90082-3","volume":"31","author":"S. Khuller","year":"1989","unstructured":"S. Khuller, On Computing Graph Closures, Inf. Proc. Lett. 31 (1989) 249\u2013255.","journal-title":"Inf. Proc. Lett."},{"key":"33_CR18","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1109\/TC.1981.6312171","volume":"C-30","author":"G.F. Lev","year":"1981","unstructured":"G.F. Lev, N. Pippenger and L.G. Valiant, A Fast Parallel Algorithm for Routing in Permutation Networks, IEEE Transactions on Computers C-30 (1981) 93\u2013100.","journal-title":"IEEE Transactions on Computers"},{"key":"33_CR19","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/0095-8956(73)90057-9","volume":"14","author":"M. Meyniel","year":"1973","unstructured":"M. Meyniel, Une condition suffisante d'existence d'un circuit Hamiltonien dans un graphe orient\u00e9, J. Comb. Theory Ser. B 14 (1973) 137\u2013147.","journal-title":"J. Comb. Theory Ser. B"},{"key":"33_CR20","doi-asserted-by":"crossref","first-page":"55","DOI":"10.2307\/2308928","volume":"67","author":"O. Ore","year":"1960","unstructured":"O. Ore, Note on Hamiltonian Circuits, Amer. Math. Monthly 67 (1960) 55.","journal-title":"Amer. Math. Monthly"},{"key":"33_CR21","doi-asserted-by":"crossref","DOI":"10.21236\/ADA619387","volume-title":"Fast Parallel Algorithms for Finding Hamiltonian Paths and Cycles in a Tournament","author":"D. Soroker","year":"1986","unstructured":"D. Soroker, Fast Parallel Algorithms for Finding Hamiltonian Paths and Cycles in a Tournament, Report no. UCB\/CSD 87\/309, Univ. of California, Berkeley 1986."},{"key":"33_CR22","first-page":"68","volume":"3","author":"K. Takamizawa","year":"1980","unstructured":"K. Takamizawa, T. Nishizeki and N. Saito, An O(p 3) Algorithm for Finding Hamiltonian Cycle in Certain Digraphs, J. Inf. Proc. 3 (1980) 68\u201372.","journal-title":"J. Inf. Proc."},{"key":"33_CR23","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1090\/S0002-9947-1956-0081471-8","volume":"82","author":"W.T. Tutte","year":"1956","unstructured":"W.T. Tutte, A Theorem on Planar Graphs, Trans. Am. Math. Soc. 82 (1956) 99\u2013116.","journal-title":"Trans. Am. Math. Soc."},{"key":"33_CR24","doi-asserted-by":"crossref","first-page":"739","DOI":"10.1112\/plms\/s3-24.4.739","volume":"24","author":"D.R. Woodall","year":"1972","unstructured":"D.R. Woodall, Sufficient Conditions for Circuits in Graphs, Proc. Lond. Math. Soc. 24 (1972) 739\u2013755.","journal-title":"Proc. Lond. Math. Soc."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-54233-7_153.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:53:17Z","timestamp":1605646397000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54233-7_153"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540542339","9783540475163"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-54233-7_153","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1991]]}}}