Computación en Paralelo


BIBLIOGRAFIA SOBRE LOS CAPITULOS 1 Y 2. 

[BLUM83]. N. Blum. A note on the "parallel computation thesis". Information Processing Letters 17, pp. 203-205. ** 

[CARLINI91]. U. de Carlini and U. Villano. Transputers and parallel architectures. message-passing distributed systems. Ellis Horwood Series in Computers and their applications. England. 

[COK91]. R.S. Cok. Parallel programs for the transputer. Prentice Hall. Englewood Clifs, NJ. 

[COOK80]. S.A. Cook. Towards a complexity theory of synchronuos parallel computation. L'Enseignement Mathematique 30. ** 

[ELLISON91]. D. Ellison. Understanding occam and the transputer. Sigma Press. England. 

[FORTUNE78]. S. Fortune and J. Wyllie. Parallelism in random access machines. Proceedings of the 10th Annual ACM Symposium on Theory of Computing, pp. 114-118. 

[FLYNN66]. M.J. Flynn. Very high-speed computing systems. Proceedings of IEEE 54 (12), pp. 1901-1909. ** 

[GEIST93]. A. Geist, A. Beguelin, J. Dongarra, W. Jiang, R. Mancheck and V. Sunderam. PVM 3.1 user's guide and reference manual. Oak Ridge laboratory. 

[GOODMAN77]. S.E. Goodman and S.T. Hedetniemi. Introduction to the design and analysis of algorithms. McGraw-Hill, NY. ** 

[HERTER93]. C.G. Herter, T.M. Warschko, W.C. Tichy and M. Philippsen. Triton/1: A massively-parallel mixed-mode computer designed to support high level languages. Proceedings of the International Parallel Processing Symposium. ** 

[HWANG85]. K. Hwang and F.A. Briggs. Computer architecture and parallel processing. McGraw-Hill. 

[INMOS88]. INMOS Limited. Occam2 reference manual. Prentice Hall. Series in Computer Science. C.A.R. Hoare Series Editor. 

[INMOS90]. INMOS Limited. AnsiC toolset reference manual. Inmos Limited. 

[KINDERVATER88]. G.A.P. Kindervater and J.K. Lenstra. Parallel computing in combinatorial optimization. Annals of Operations Research 14, pp. 245-289. ** 

[PARBERRY87]. I. Parberry. Parallel complexity theory. John Wiley & Sons. NY. 

(* OJO *) 

[POUNTAIN91]. D. Pountain. The transputer strikes back. BYTE OJO, pp. 265-275. 

[QUINN94]. M.J. Quinn. Parallel computing: Theory and practice. McGraw-Hill. OR. 

[RODA94]. J.L. Roda. Computaci¢n distribu¡da sobre redes heterog‚eneas: El entorno PVM. Memoria de Licenciatura. Dept. Estadistica, Inv. Operativa y Computacion, Univ. de La Laguna. 

[SHILOACH81]. Y. Shiloach and U. Vishkin. Finding the maximun, sorting and merging in a parallel computation model. Journal of Algorithms 2 (1), pp. 88-102. ** 


BIBLIOGRAFIA DIVIDE Y VENCERAS. CAPITULO 3. 

[AHO74]. A.V. Aho, J.E. Hopcroft and J.D. Ullman. The design and analysis of computer algorithms. Addison-Wesley. Reading, MA. 

[AHO83]. A.V. Aho, J.E. Hopcroft and J.D. Ullman. Data structures and algorithms. Addison-Wesley. Reading, MA. 

[AKL85]. S.G. Akl. Parallel sorting algorithms. Academic Press. Orlando, FL. ** 

[BRINCH91]. P. Brinch Hansen. Parallel divide and conquer. Technical Report, School of Computer and Information Science, Syracuse University, Syracuse, NY. 

[BRINCH94]. P. Brinch Hansen. Do hypercubes sort faster than tree machines?. Concurrency: Practice and Experience 6 (2), pp 143- 151. 

[CHANDRA93]. S. Chandra, M. Jain, A. Basu and P.S. Kumar. Sorting algorithms on transputer arrays. Parallel Computing 19, pp. 595- 607. 

[CHEN84]. J. Chen, E.L. Dagless and Y. Guo. Performance measurements of scheduling strategies and parallel algorithms for a multiprocessor quick sort. IEE Proceedings, Part E, Computers and Digital Techniques 131, pp. 45-54. ** 

[CHIBA90]. S. Chiba, H. Honda, H. Maezawa, T. Tsukioka, M. Uematsu, Y. Yoshida and K. Maeda.Divide and conquer in parallel procesing. Proceedings of the 3rd Transputer/Occam International Conference, pp. 279-293. Tokyo, Japan. IOS Press. 

[CLAYTON94]. P.G. Clayton, R.C. Watkins and E.P. Wentworth. A pilot implementation of some algorithmic skeletons on transputers. Proceedings of the 7th Conference of the North American Transputer Users Group, pp. 295-302. Atlanta. GA. IOS Press. 

[DEMINET82]. J. Deminet. Experiences with multiprocessor algorithms. IEEE Transactions on Computers C-31 (4), pp. 278-288 ** 

[EVANS85]. D.J. Evans and N.Y. Yousif. Analysis of the performance of the parallel quicksort method. BIT 25, pp. 106- 112. ** 

[HOARE62] . C.A.R. Hoare. Quicksort. The Computer Journal 5, pp. 10-15. ** 

[HOROWITZ78]. E. Horowitz and S. Sahni. Fundamentals of computer algorithms. Computer Science Press. Potomac, MD. 

[JACQUEMIN90]. J.L. Jacquemin and M. Griffiths. Implementing recursion on a double ring topology. Proceedings of the 3rd Transputer/Occam International Conference, pp. 57-62. Tokyo, Japan. IOS Press. 

[KIM92]. D. Kim and Y. Hah. A parallel TSP algorithm based on divide and conquer strategy. Parallel Computing and Transputer Applications, pp 119-127. Barcelona. CIMNE, IOS Press. 

[KINDERVATER88]. G.A.P. Kindervater and H.W.J.M. Trienekens. Experiments with parallel algorithms for combinatorial problems. European Journal of Operational Research 33, pp. 65-81. 

[LEON91]. C. Le¢n. Un compilador pascal paralelo para el modelo P-RAM. Memoria de Licenciatura. Dept. Estadistica, Inv. Operativa y Computacion, Univ. de La Laguna. 

[LI93]. X. Li, P. Lu, J. Schaeffer, J. Shillington, P.S. Wong and H. Shi. On the versatility of parallel sorting by regular sampling. Parallel Computing 19, pp. 1079-1103. 

[PETERS81]. F.J. Peters. Tree machines and divide-and-conquer algorithms. Proceedings of the CONPAR 81, pp. 25-36. Springer Verlag Berlin. 

[QUINN88]. M.J. Quinn. Parallel sorting algorithms for tightly coupled multiprocessors. Parallel Computing 6, pp. 349-357. 

[QUINN94]. M.J. Quinn. Parallel computing: Theory and practice. McGraw-Hill. OR. 

[ROTEM85]. D. Rotem, N. Santoro and J. Sidney. Distributed sorting. IEEE Transactions on Computers C-34 (4), pp. 372-376. 

[TODD78]. S. Todd. Algorithms and hardware for a merge sort using multiple processors. IBM Journal of Research and Development 22 (5), pp. 509-517. ** 

[VARMAN92]. P.T. Varman and K. Doshi. Sorting with linear speedup on a pipelined hypercube. IEEE Transactions on Computers 41 (1), pp. 97-103. 

[WAGAR86]. B. Wagar. Hyperquicksort: A fast sorting algorithm for hypercubes. Proceedings of 2nd Conference on Hypercube Multiprocessors, pp. 292-299. ** 

[WHEAT92]. M. Wheat and D.J. Evans. An efficient parallel sorting algorithm for shared memory multiprocessors. Parallel Computing 18, pp. 91-102. 

[WIRTH76]. N. Wirth. Algorithms + data structures = programs. Prentice-Hall. Englewood Cliffs, NJ. 

[WON89]. H.Won and S. Sahni. Hypercube-to-host sorting. J. Supercomputing, 3 (1). pp. 41-61. ** 


BIBLIOGRAFIA SOBRE PROGRAMACION DINAMICA. CAPITULO 4. 

[AHO74]. A.V. Aho, J.E. Hopcroft and J.D. Ullman. The design and analysis of computer algorithms. Addison-Wesley. Reading, MA. 

[AHO83]. A.V. Aho, J.E. Hopcroft and J.D. Ullman. Data structures and algorithms. Addison-Wesley. Reading, MA. 

[ALMEIDA94]. F. Almeida, D. Morales, F. Garc¡a and C. Rodr¡guez. Transputers Applications and Systems '94, pp 817-831. Italy. IOS Press, Ohmsha. 

[ALMEIDA95]. F. Almeida, F. Garc¡a, D. Morales and C. Rodr¡guez. A parallel algorithm for the integer knapsack problem for pipeline networks. to appear in Journal of Parallel Algorithms and Applications 6 (3/4). 

[CHEN92]. G. Chen and J. Jang. An improved parallel algorithm for 0/1 knapsack problem. Parallel Computing 18, pp. 811-821. 

[HOROWITZ78]. E. Horowitz and S. Sahni. Fundamentals of computer algorithms. Computer Science Press. Potomac, MD. 

[IBARAKI87]. T. Ibaraki. Enumerative approaches to combinatorial optimization. Part II. J.C. BALTZER AG. Basel, Switzerland. 

[KINDERVATER88]. G.A.P. Kindervater and H.W.J.M. Trienekens. Experiments with parallel algorithms for combinatorial problems. European Journal of Operational Research 33, pp. 65-81. 

[LEE88]. J. Lee, E. Shragowitz and S. Sahni. A hypercube algorithm for the 0/1 knapsack problem. Journal of Parallel and Distributed Computing 5, pp. 438-456. 

[LI85]. G. Li and B.W. Wah. Systolic processing for Dynamic Programming. Proceedings of 1985 International Conference on Parallel Processing, pp. 434-441. ** 

[LIN91]. J. Lin and J.A. Storer. Processor-efficient hypercube algorithms for the knapsack problem. Journal of Parallel and Distributed Computing 11, pp. 332-337. 

[MARTELLO90]. S. Martello and P. Toth. Knapsack problems: Algorithms and computer implementations. John Wiley & Sons. England. 

[MOLDOVAN86]. D.I. Moldovan and J.A.B. Fortes. Partitioning and mapping algorithms into fixed size systolic arrays. IEEE Transactions on Computers C-35 (1), pp. 1-12. ** 

[SEDGEWICK83]. R. Sedgewick. Algorithms. Addison-Wesley. Reading, MA. 

[SMITH91]. D.K. Smith. Dynamic programming: A practical introduction. Ellis Horwood. England. 

[SYSLO83]. M.M. Syslo, N. Deo and J.S. Kowalik. Discrete optimization algorithms with pascal programs. Prentice-Hall. Englewood Cliffs, NJ. 

[TENG90]. S. Teng. Adaptative parallel algorithms for integral knapsack problem. Journal of Parallel and Distributed Computing 8, pp. 400-406. 

[ULM92]. D.R. Ulm and P.Y. Wang. Solving a two dimensional knapsack problem on SIMD computers. Proceedings of 1992 International Conference on Parallel Processing. 


BIBLIOGRAFIA SOBRE RAMIFICACION Y ACOTACION. CAPITULO 5. 

[AHO74]. A.V. Aho, J.E. Hopcroft and J.D. Ullman. The design and analysis of computer algorithms. Addison-Wesley. Reading, MA. 

[AHO83]. A.V. Aho, J.E. Hopcroft and J.D. Ullman. Data structures and algorithms. Addison-Wesley. Reading, MA. 

[AKL82]. S.G. Akl, D.T. Barnard and R.J. Doran. Design, analysis, and implementation of a parallel tree search algorithm. IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI 4 (2), pp 192-203. 

[ALMEIDA92]. F. Almeida. Paralelismo: Utilidades y aplicaciones en programaci¢n combinatoria. Memoria de Licenciatura. Dept. Estadistica, Inv. Operativa y Computacion, Univ. de La Laguna. 

[BOFFEY91]. T.B. Boffey and P. Saeidi. Parallel branch-and-bound using shared memory. Technical Report, SCM Dept. University of Liverpool. ** 

[BURTON82]. F.W. Burton. G.P. Mckeown, V.J. Rayward-Smith and M.R. Sleep. Parallel processing and combinatorial optimisation. Proceedings of the Combinatorial Optimisation III Conference, pp. 19-36. Stirling. ** 

[CAPEL92]. M. Capel and A. Palma. A programming tool for distributed implementation of branch-and-bound algorithms. Parallel Computing and Transputer Applications, pp. 138-147. Barcelona. CIMNE, IOS Press. 

[EL-DESSOUKI80]. O.I. El-Dessouki and W.H. Huen. Distributed enumeration on network computers. IEEE Transactions on Computers C-29 (9) pp. 818-825. 

[HELD70]. M. Held and R.M. Karp. The traveling salesman problem and minimum spanning trees. Operations Research 18, pp. 1138- 1162. ** 

[HELD71]. M. Held and R.M. Karp. The traveling salesman problem and minimum spanning trees: part II. Mathematical Programming 1, pp. 6-25. ** 

[HOROWITZ78]. E. Horowitz and S. Sahni. Fundamentals of computer algorithms. Computer Science Press. Potomac, MD. 

[IBARAKI87]. T. Ibaraki. Enumerative approaches to combinatorial optimization. Part I-II. J.C. BALTZER AG. Basel, Switzerland. 

[KINDERVATER88]. G.A.P. Kindervater and J.K. Lenstra. Parallel computing in combinatorial optimization. Annals of Operations Research 14, pp. 245-289. ** 

[KINDERVATER88]. G.A.P. Kindervater and H.W.J.M. Trienekens. Experiments with parallel algorithms for combinatorial problems. European Journal of Operational Research 33, pp. 65-81. 

[LAI84]. T. Lai and S. Sahni. Anomalies in parallel branch-and- bound algorithms. Communications of the ACM 27 (6), pp. 594-602. 

[LAI85]. T. Lai and A. Sprague. Performance of parallel branch- and-bound algorithms. IEEE Transactions on Computers C-34 (10), pp. 962-964. 

[LAWLER85]. E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys. The traveling salesman problem. A guided tour of combinatorial optimization. John Wiley & Sons. England. 

[LEE94]. Y.N. Lee, G.P. Mckeown and V.J. Rayward-Smith. Solving the convoy movement problem using branch-and-bound on a network of transputers. Transputers Applications and Systems '94, pp 786- 796. Italy. IOS Press, Ohmsha. 

[LITTLE63]. J.D.C. Little, K.G. Murty, D.W. Sweeney and C. Karel. An algorithm for the travelling salesman problem. Operations Research 11 (6), pp. 972-989. ** 

[LOOTS92]. W. Loots and T.H.C. Smith. A parallel algorithm for the 0-1 knapsack problem. International Journal of Parallel Programming 21 (5), pp. 349-362. 

[LšING89]. R. Ling and B. Monien. Two strategies for solving the vertex cover problem on a transputer network. 3rd International Workshop on Distributed Algorithms, LNCS392, pp. 160-171. ** 

[LšING91]. R. Ling, B. Monien and F. Ramme. Load balancing in large networks: A comparative study. Proceedings of the 3th IEEE Symposium on Parallel and Distributed Processing. 

[MARTELLO90]. S. Martello and P. Toth. Knapsack problems: Algorithms and computer implementations. John Wiley & Sons. England. 

[MCKEOWN91]. G.P. Mckeown, V.J. Rayward-Smith, A. Rush and H.J. Turpin. Using a transputer network to solve branch-and-bound problems. Proceedings of the TRANSPUTING '91 Conference, pp. 781- 800. IOS Press. 

[MOHAN83]. J. Mohan. Experience with two parallel programs solving the travelling salesman problem. Proceedings of the 1983 International Conference on Parallel Processing, pp. 191-193. IEEE, NY. ** 

[MONIEN87]. B. Monien and O. Vornberger. Parallel procesing of combinatorial search trees. Proceedings of International Workshop on Parallel Algorithms and Architectures, pp. 60-69. Springer Verlag Berlin. 

[QUINN90]. M.J. Quinn. Analysis and implementation of branch - and-bound algorithms on a hypercube multicomputer. IEEE Transactions on Computers C-39 (3), pp. 384-387. ** 

[QUINN94]. M.J. Quinn. Parallel Computing: Theory and practice. McGraw-Hill. OR. 

[RODRIGUEZ92]. C. Rodr¡guez, F. Garcia, C. Le¢n y F. Almeida. A parallelization of a branch and bound algorithm for the set covering problem. Proceedings of the VI Meeting of the EURO Working Group on Location Analysis, pp. 183-193. 

[SYSLO83]. M.M. Syslo, N. Deo and J.S. Kowalik. Discrete optimization algorithms with pascal programs. Prentice-Hall. Englewood Cliffs, NJ. 

[TAUDES91]. A. Taudes and T. Netousek. Implementing branch-and- bound algorithms on a cluster of workstations. A survey, some new results and open problems. Proceedings of the workshop on parallel algorithms and Tranputers for optimization, pp. 79-102. Siegen. Springer-Verlag. 

[TOPOR84]. R.W. Topor. Termination detection for distributed computations. Information Processing Letters 18, pp. 33-36. ** 

[TROYA89]. J.M. Troya and M. Ortega. A study of parallel branch- and-bound algorithms with best-bound-first search. Parallel Computing 11, pp 121-126. 

[VORNBERGER86]. O. Vornberger. Implementing branch-and-bound in a ring of processors. Proceedings of CONPAR 86, LNCS 237, pp. 157-164. Springer Verlag. ** 

[VORNBERGER88]. O. Vornberger. Load balancing in a network of transputers. Distributed Algorithms, LNCS 312, pp. 116-126. Springer Verlag. ** 

[WAH84]. B.W. Wah and Y.W. Eva Ma. MANIP - A multicomputer architecture for solving combinatorial extremum-search problems. IEEE Transactions on Computers C-33 (5), pp. 377-390. 

[WAH85]. B.W. Wah, G. Li and C.F. Yu. Multiprocessing of combinatorial search problems. Computer 18 (6), pp. 93-108. 


BIBLIOGRAFIA SOBRE HEURISTICAS 

[AZE92] Azencot. Simulated Annealing: Parallelization Techniques. John wiley. 1992. 

[MIC92]. Z. Michaelewicz. Genetic Algorithms + Data Structures = Evolution Programs. Springer Verlag. 1992. 
 

 
[Home] [Gias Members] [Ph D Program] [Projects] [Publications] [FTP] [WWW Links] [Statistics] 
 

Grupo de Inteligencia Artificial y Sistemas (GIAS)
Dpto. Informática y Sistemas
Universidad Las Palmas de Gran Canaria
35017 Las Palmas. SPAIN