@inproceedings{8b5c12f28abb4bbb9753607d3c57c881,
title = "Techniques for designing efficient parallel graph algorithms for SMPs and multicore processors",
abstract = "Graph problems are finding increasing applications in high performance computing disciplines. Although many regular problems can be solved efficiently in parallel, obtaining efficient implementations for irregular graph problems remains a challenge. We propose techniques for designing and implementing efficient parallel algorithms for graph problems on symmetric multiprocessors and chip multiprocessors with a case study of parallel tree and connectivity algorithms. The problems we study represent a wide range of irregular problems that have fast theoretic parallel algorithms but no known efficient parallel implementations that achieve speedup without serious restricting assumptions about the inputs. We believe our techniques will be of practical impact in solving large-scale graph problems.",
keywords = "Biconnected components, Minimum spanning tree, Shared memory, Spanning tree",
author = "Guojing Cong and Bader, {David A.}",
year = "2007",
doi = "10.1007/978-3-540-74742-0_15",
language = "English",
isbn = "3540747419",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "137--147",
booktitle = "Parallel and Distributed Processing and Applications - 5th International Symposium, ISPA 2007, Proceedingsq",
note = "5th International Symposium on Parallel and Distributed Processing and Applications, ISPA 2007 ; Conference date: 29-08-2007 Through 31-08-2007",
}