{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T15:38:03Z","timestamp":1781105883797,"version":"3.54.1"},"reference-count":0,"publisher":"IGI Global Scientific Publishing","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016,10,1]]},"abstract":"<p>In this paper, the authors highlight the existence of close relations between the execution time, efficiency and number of communication rounds in a family of CGM-based parallel algorithms for the optimal binary search tree problem (OBST). In this case, these three parameters cannot be simultaneously improved. The family of CGM (Coarse Grained Multicomputer) algorithms they derive is based on Knuth's sequential solution running in  time and  space, where n is the size of the problem. These CGM algorithms use p processors, each with  local memory. In general, the authors show that each algorithms runs in  with  communications rounds.  is the granularity of their model, and  is a parameter that depends on  and . The special case of  yields a load-balanced CGM-based parallel algorithm with  communication rounds and  execution steps. Alternately, if , they obtain another algorithm with better execution time, say , the absence of any load-balancing and  communication rounds, i.e., not better than the first algorithm. The authors show that the granularity has a crucial role in the different techniques they use to partition the problem to solve and study the impact of each scheduling algorithm. To the best of their knowledge, this is the first unified method to derive a set of parameter-dependent CGM-based parallel algorithms for the OBST problem.<\/p>","DOI":"10.4018\/ijghpc.2016100104","type":"journal-article","created":{"date-parts":[[2016,11,29]],"date-time":"2016-11-29T10:56:40Z","timestamp":1480417000000},"page":"55-77","source":"Crossref","is-referenced-by-count":4,"title":["High Performance CGM-based Parallel Algorithms for the Optimal Binary Search Tree Problem"],"prefix":"10.4018","volume":"8","author":[{"given":"Vianney Kengne","family":"Tchendji","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computer Science, University of Dschang, Dschang, Cameroon"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jean Frederic","family":"Myoupo","sequence":"additional","affiliation":[{"name":"University of Picardie Jules Verne, Amiens, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gilles","family":"Dequen","sequence":"additional","affiliation":[{"name":"University of Picardie Jules Verne, Amiens, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"2432","container-title":["International Journal of Grid and High Performance Computing"],"original-title":[],"language":"ng","link":[{"URL":"https:\/\/www.igi-global.com\/viewtitle.aspx?TitleId=172505","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,1]],"date-time":"2022-06-01T19:41:21Z","timestamp":1654112481000},"score":1,"resource":{"primary":{"URL":"https:\/\/services.igi-global.com\/resolvedoi\/resolve.aspx?doi=10.4018\/IJGHPC.2016100104"}},"subtitle":[""],"short-title":[],"issued":{"date-parts":[[2016,10,1]]},"references-count":0,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,10]]}},"URL":"https:\/\/doi.org\/10.4018\/ijghpc.2016100104","relation":{},"ISSN":["1938-0259","1938-0267"],"issn-type":[{"value":"1938-0259","type":"print"},{"value":"1938-0267","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,10,1]]}}}