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 largescale
graph problems.
