{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T01:30:27Z","timestamp":1649122227457},"reference-count":27,"publisher":"Elsevier BV","issue":"4","license":[{"start":{"date-parts":[[1986,4,1]],"date-time":"1986-04-01T00:00:00Z","timestamp":512697600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information Processing Letters"],"published-print":{"date-parts":[[1986,4]]},"DOI":"10.1016\/0020-0190(86)90021-9","type":"journal-article","created":{"date-parts":[[2003,3,14]],"date-time":"2003-03-14T14:37:33Z","timestamp":1047652653000},"page":"163-169","source":"Crossref","is-referenced-by-count":4,"title":["An efficient algorithm for the transitive closure and a linear worst-case complexity result for a class of sparse graphs"],"prefix":"10.1016","volume":"22","author":[{"given":"Brigitte","family":"Jaumard","sequence":"first","affiliation":[]},{"given":"Michel","family":"Minoux","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0020-0190(86)90021-9_BIB1","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/BF00264600","article-title":"Improved time and space bounds for boolean multiplication","volume":"11","author":"Adleman","year":"1978","journal-title":"Acta Informatica"},{"key":"10.1016\/0020-0190(86)90021-9_BIB2","first-page":"195","article-title":"The Design and Analysis of Computer Algorithms","author":"Aho","year":"1974"},{"issue":"5","key":"10.1016\/0020-0190(86)90021-9_BIB3","first-page":"1209","article-title":"On economical construction of the transitive closure of an oriented graph","volume":"11","author":"Arlazarov","year":"1970","journal-title":"Soviet Math. Dokl."},{"key":"10.1016\/0020-0190(86)90021-9_BIB4","series-title":"Automata, Languages and Programming","first-page":"425","article-title":"A note on the average time to compute transitive closure","author":"Bloniarz","year":"1976"},{"key":"10.1016\/0020-0190(86)90021-9_BIB5","doi-asserted-by":"crossref","DOI":"10.1145\/1008361.1008362","article-title":"Boolean matrix multiplication using only O(nlog7(log n) bit operations","author":"Booth","year":"1977","journal-title":"SIGACT News"},{"issue":"3","key":"10.1016\/0020-0190(86)90021-9_BIB6","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1137\/0211038","article-title":"On the asymptotic complexity of matrix multiplication","volume":"11","author":"Coppersmith","year":"1982","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0020-0190(86)90021-9_BIB7","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/BF02252839","article-title":"An algorithm for finding the transitive closure of a relation","volume":"15","author":"Dzikiewicz","year":"1975","journal-title":"Comput."},{"issue":"5","key":"10.1016\/0020-0190(86)90021-9_BIB8","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0020-0190(81)90026-0","article-title":"A sensitive transitive closure algorithm","volume":"12","author":"Ebert","year":"1981","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0020-0190(86)90021-9_BIB9","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1007\/BF00271339","article-title":"On computing the transitive closure of a relation","volume":"8","author":"Eve","year":"1977","journal-title":"Acta Informatica"},{"key":"10.1016\/0020-0190(86)90021-9_BIB10","series-title":"12th Ann. IEEE Symp. on Switching and Automata Theory","first-page":"129","article-title":"Boolean matrix multiplication and transitive closure","author":"Fischer","year":"1971"},{"issue":"6","key":"10.1016\/0020-0190(86)90021-9_BIB11","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1145\/358876.358884","article-title":"A more general algorithm for computing closed semiring costs between vertices of a directed graph","volume":"23","author":"Fletcher","year":"1980","journal-title":"Comm. ACM"},{"key":"10.1016\/0020-0190(86)90021-9_BIB12","first-page":"1252","article-title":"Application of a method of fast multiplication of matrices in the problem of finding the transitive closure of graph","volume":"11","author":"Furman","year":"1970","journal-title":"Soviet Math. Dokl."},{"key":"10.1016\/0020-0190(86)90021-9_BIB13","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/0020-0190(76)90079-X","article-title":"A cascade algorithm for the logical closure of a set of binary relations","volume":"2","author":"Hansen","year":"1976","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0020-0190(86)90021-9_BIB14","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1016\/0196-6774(80)90017-6","article-title":"Linear-time algorithms for connectivity problems","volume":"1","author":"Karp","year":"1980","journal-title":"J. Algorithms"},{"key":"10.1016\/0020-0190(86)90021-9_BIB15","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/0304-3975(77)90056-1","article-title":"Algebraic structures for transitive closure","volume":"4","author":"Lehmann","year":"1977","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0020-0190(86)90021-9_BIB16","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/0020-0190(71)90006-8","article-title":"Efficient determination of the transitive closure of a directed graph","author":"Munro","year":"1971","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0020-0190(86)90021-9_BIB17","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/S0019-9958(73)90228-3","article-title":"A fast expected time algorithm for boolean matrix multiplication and transitive closure","volume":"22","author":"O'Neil","year":"1973","journal-title":"Inform. and Control"},{"key":"10.1016\/0020-0190(86)90021-9_BIB18","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1007\/BF01940892","article-title":"A transitive closure algorithm","volume":"10","author":"Purdom","year":"1970","journal-title":"BIT"},{"key":"10.1016\/0020-0190(86)90021-9_BIB19","article-title":"A systolic array for the algebraic path problems","author":"Rote","year":"1983"},{"key":"10.1016\/0020-0190(86)90021-9_BIB20","first-page":"216","article-title":"Transitivit\u00e9 et connexit\u00e9","volume":"249","author":"Roy","year":"1959","journal-title":"Compt. Rend. Acad. Sci. Paris"},{"key":"10.1016\/0020-0190(86)90021-9_BIB21","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/BF02242140","article-title":"An improved transitive closure algorithm","volume":"30","author":"Schmitz","year":"1983","journal-title":"Comput."},{"issue":"2","key":"10.1016\/0020-0190(86)90021-9_BIB22","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1137\/0207011","article-title":"An algorithm for transitive closure with linear expected time","volume":"7","author":"Schnorr","year":"1978","journal-title":"SIAM J. Comput"},{"key":"10.1016\/0020-0190(86)90021-9_BIB23","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1007\/BF02165411","article-title":"Gaussian elimination is not optimal","volume":"13","author":"Strassen","year":"1969","journal-title":"Numer. Math."},{"key":"10.1016\/0020-0190(86)90021-9_BIB24","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/BF02252834","article-title":"Computational experiences with some transitive algorithms","volume":"15","author":"Sys\u0142o","year":"1975","journal-title":"Comput."},{"issue":"2","key":"10.1016\/0020-0190(86)90021-9_BIB25","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","article-title":"Depth-first search and linear graph algorithms","volume":"1","author":"Tarjan","year":"1972","journal-title":"SIAM J. Comput."},{"issue":"4","key":"10.1016\/0020-0190(86)90021-9_BIB26","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1145\/360715.360746","article-title":"A modification of Warshall's algorithm for the transitive closure of binary relations","volume":"18","author":"Warren","year":"1975","journal-title":"Comm. ACM"},{"key":"10.1016\/0020-0190(86)90021-9_BIB27","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1145\/321105.321107","article-title":"A theorem on boolean matrices","volume":"9","author":"Warshall","year":"1962","journal-title":"J. Assoc. Comput. Mach."}],"container-title":["Information Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0020019086900219?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0020019086900219?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,3,26]],"date-time":"2019-03-26T05:29:29Z","timestamp":1553578169000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0020019086900219"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,4]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1986,4]]}},"alternative-id":["0020019086900219"],"URL":"https:\/\/doi.org\/10.1016\/0020-0190(86)90021-9","relation":{},"ISSN":["0020-0190"],"issn-type":[{"value":"0020-0190","type":"print"}],"subject":[],"published":{"date-parts":[[1986,4]]}}}