{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T08:51:02Z","timestamp":1648975862086},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2006,10,1]],"date-time":"2006-10-01T00:00:00Z","timestamp":1159660800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Supercomput"],"published-print":{"date-parts":[[2006,10]]},"DOI":"10.1007\/s11227-006-9157-5","type":"journal-article","created":{"date-parts":[[2006,9,15]],"date-time":"2006-09-15T04:41:29Z","timestamp":1158295289000},"page":"83-107","source":"Crossref","is-referenced-by-count":3,"title":["Work-efficient BSR-based parallel algorithms for some fundamental problems in graph theory"],"prefix":"10.1007","volume":"38","author":[{"given":"Jean-Fr\u00e9d\u00e9ric","family":"Myoupo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Sem\u00e9","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"9157_CR1","volume-title":"The design and analysis of computer algorithms","author":"AV Aho","year":"1974","unstructured":"Aho AV, Hopcroft JE, Ullman JD (1974) The design and analysis of computer algorithms. Addison-Wesley, Reading, MA"},{"key":"9157_CR2","volume-title":"Parallel computation: Models and methods","author":"SG Akl","year":"1997","unstructured":"Akl SG (1997) Parallel computation: Models and methods, Prentice Hall, Upper Saddle River, NJ"},{"key":"9157_CR3","unstructured":"Akl SG, Guenther GR (1989) Broadcasting with selective reduction. In: Information Processing 89, Ritter GX (ed) Proceedings of the IFIP 11th world computer congress. North\u2013Holland, San Francisco, pp 515\u2013520"},{"key":"9157_CR4","doi-asserted-by":"crossref","unstructured":"Akl SG, Stojmenovic I (1994) Multiple criteria BSR: An implementation and applications to computational geometry problems. In: Proceedings of the twenty-seventh annual hawaii international conference on system sciences","DOI":"10.1109\/HICSS.1994.323269"},{"key":"9157_CR5","first-page":"192","volume-title":"Parallel and distributed computing handbook","author":"SG Akl","year":"1996","unstructured":"Akl SG, Stojmenovic I (1996) Broadcasting with selective reduction: A powerful model of parallel computation. In: AY Zomaya (ed) Parallel and distributed computing handbook. McGraw-Hill, New York, pp 192\u2013222"},{"key":"9157_CR6","first-page":"1209","volume":"11","author":"VL Arlazarov","year":"1970","unstructured":"Arlazarov VL, Dinic EA, Kronrod MA, Faradzev IA (1970) On economical construction of the transitive closure of a directed graph. Soviet Math Dokl 11:1209\u20131210","journal-title":"Soviet Math Dokl"},{"issue":"3","key":"9157_CR7","doi-asserted-by":"crossref","first-page":"649","DOI":"10.1145\/828.322449","volume":"31","author":"MJ Atallah","year":"1984","unstructured":"Atallah MJ, Kosaraju SR (1984) Graph problems on a mesh-connected processor array. J Assoc Comput Mach 31(3):649\u2013667","journal-title":"J Assoc Comput Mach"},{"key":"9157_CR8","first-page":"517","volume":"10","author":"L Auslander","year":"1961","unstructured":"Auslander L, Parter SV (1961) On embedding graphs in the plane. J Math Mech 10:517\u2013523","journal-title":"J Math Mech"},{"key":"9157_CR9","volume-title":"The theory of graphs and its applications","author":"C Berge","year":"1962","unstructured":"Berge C (1962) The theory of graphs and its applications. John Wiley and Sons, New York"},{"key":"9157_CR10","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-9967-7","volume-title":"Graph Theory: An introductory course","author":"B Bollob\u00e1s","year":"1979","unstructured":"Bollob\u00e1s B (1979) Graph Theory: An introductory course. Springer Verlag, New York"},{"key":"9157_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-349-03521-2","volume-title":"Graph theory with applications","author":"JA Bondy","year":"1976","unstructured":"Bondy JA, Murty USR (1976) Graph theory with applications. Elsevier North-Holland, New York"},{"issue":"1","key":"9157_CR12","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1142\/S0129626499000104","volume":"9","author":"E Delacourt","year":"1999","unstructured":"Delacourt E, Myoupo JF, Sem\u00e9 D (1999) A constant time parallel detection of repetition. Parall Proc Lett 9(1):81\u201392","journal-title":"Parall Proc Lett"},{"issue":"3","key":"9157_CR13","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1109\/71.210809","volume":"4","author":"L Fava Lindon","year":"1993","unstructured":"Fava Lindon L, Akl SG (1993) An optimal implantation of broadcasting with selective reduction. IEEE Trans Paral Distr Syst 4(3):256\u2013269","journal-title":"IEEE Trans Paral Distr Syst"},{"key":"9157_CR14","unstructured":"Guibas LJ, Kung HT, Thompson CD (1979) Direct VLSI implementation of combinatorial algorithm. In: Proc. Caltech Conference on VLSI, pp 509\u2013525"},{"key":"9157_CR15","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/BF01952677","volume":"29","author":"TS Huang","year":"1989","unstructured":"Huang TS, Tsai MS (1989) A linear systolic algorithm for the connected component problem. BIT 29:217\u2013226","journal-title":"BIT"},{"issue":"5","key":"9157_CR16","doi-asserted-by":"crossref","first-page":"603","DOI":"10.1109\/TC.1987.1676945","volume":"C36","author":"SY Kung","year":"1987","unstructured":"Kung SY, Lo SC, Lewis PS (1987) Optimal systolic design for the transitive closure and shortest path problems. IEEE Trans Comput C36(5):603\u2013614","journal-title":"IEEE Trans Comput"},{"key":"9157_CR17","unstructured":"Manber U (1989) Introduction to algorithms: A creative approach. Addison-Wesley"},{"key":"9157_CR18","unstructured":"Myoupo JF, Sem\u00e9 D (1997) A parallel solution of the sequence alignment problem using BSR model. In: Proc. of the 10th international conference of parallel and distributed computing systems. pp 357\u2013362"},{"key":"9157_CR19","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1006\/jpdc.1999.1534","volume":"57","author":"JF Myoupo","year":"1999","unstructured":"Myoupo JF, Sem\u00e9 D (1999) Time-efficient parallel algorithms for the longest common subsequence and related problems. J Parall Distri Comput 57:212\u2013223","journal-title":"J Parall Distri Comput"},{"key":"9157_CR20","first-page":"187","volume":"14","author":"JF Myoupo","year":"2000","unstructured":"Myoupo JF, Sem\u00e9 D (2000) Efficient parallel algorithms for the LIS and LCS problems on BSR model using constant number of selections. Parall Alg Appl 14:187\u2013202","journal-title":"Parall Alg Appl"},{"issue":"1","key":"9157_CR21","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1023\/A:1013587415197","volume":"21","author":"JF Myoupo","year":"2002","unstructured":"Myoupo JF, Sem\u00e9 D (2002) Optimal BSR solutions to several convex polygon problems. J Supercomput 21(1):77\u201390","journal-title":"J Supercomput"},{"key":"9157_CR22","doi-asserted-by":"crossref","unstructured":"Ramakrishnan IV, Varman PJ (1984) Dynamic programming and transitive closure on linear pipelines. In: Proc ICPP","DOI":"10.21236\/ADA143527"},{"key":"9157_CR23","unstructured":"Sem\u00e9 D (1999) An efficient algorithm on the BSR-based parallel architecture for the k-LCS problem. In: Proc Int Conf Parall Distr Proc Techn Appl (to appear 1999)"},{"issue":"2","key":"9157_CR24","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1109\/71.485530","volume":"7","author":"I Stojmenovic","year":"1996","unstructured":"Stojmenovic I (1996) Constant time BSR solutions to parenthesis matching, tree decoding, and tree reconstitution from its traversals. IEEE Trans Parall Distr Syst 7(2):218\u2013224","journal-title":"IEEE Trans Parall Distr Syst"},{"issue":"4","key":"9157_CR25","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1109\/71.80177","volume":"1","author":"BF Wang","year":"1990","unstructured":"Wang BF, Chen GH (1990) Constant time algorithms for the transitive closure and some related graph problems on processor arrays with reconfigurable bus systems. IEEE Trans Parall Distr Syst 1(4):500\u2013507","journal-title":"IEEE Trans Parall Distr Syst"}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-006-9157-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11227-006-9157-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-006-9157-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T10:23:55Z","timestamp":1559384635000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11227-006-9157-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,10]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,10]]}},"alternative-id":["9157"],"URL":"https:\/\/doi.org\/10.1007\/s11227-006-9157-5","relation":{},"ISSN":["0920-8542","1573-0484"],"issn-type":[{"value":"0920-8542","type":"print"},{"value":"1573-0484","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,10]]}}}