Efficient Parallel Algorithms for Permutation Graphs |
| |
| Affiliation: | 1. Department of Microbiology and Molecular Genetics, Michigan State University, East Lansing, MI, USA;2. Department of Physics and Astronomy, Michigan State University, East Lansing, MI, USA;3. Department of Computer Science and Engineering, Michigan State University, East Lansing, MI, USA;4. Department of Integrative Biology, Michigan State University, East Lansing, MI, USA;5. BEACON Center for the Study of Evolution in Action, Michigan State University, East Lansing, MI, USA;1. Bioinformatics Group, Department of Computer Science & Interdisciplinary Center for Bioinformatics, Universität Leipzig, Härtelstraße 16–18, D-04107 Leipzig, Germany;2. Institute for Theoretical Computer Science, Universität zu Lübeck, Ratzeburger Allee 160, D-23562 Lübeck, Germany;3. Swarm Intelligence and Complex Systems Group, Faculty of Mathematics and Computer Science, University of Leipzig, Augustusplatz 10, D-04109 Leipzig, Germany;4. Santa Fe Institute, 1399 Hyde Park Rd., NM-87501, Santa Fe, USA;5. Faculdad de Ciencias, Universidad Nacional de Colombia, Sede Bogotá, Ciudad Universitaria, COL-111321, Bogotá, D.C., Colombia;6. Max Planck Institute for Mathematics in the Sciences, Inselstraße 22, D-04103 Leipzig, Germany;7. Institute for Theoretical Chemistry, University of Vienna, Währingerstrasse 17, A-1090 Vienna, Austria;8. Department of Mathematics, Faculty of Science, Stockholm University, SE - 106 91 Stockholm, Sweden |
| |
| Abstract: | In this paper, we present optimal O(log n) time, O(n/log n) processor EREW PRAM parallel algorithms for finding the connected components, cut vertices, and bridges of a permutation graph. We also present an O(log n) time, O(n) processor, CREW PRAM model parallel algorithm for finding a Breadth First Search (BFS) spanning tree of a permutation graph rooted at vertex 1 and use the same to derive an efficient parallel algorithm for the All Pairs Shortest Path problem on permutation graphs. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
