An Experimental Comparison of Parallel Algorithms for Ear Decomposition of Graphs using Two Leading Paradigms
David A. Bader, Ajith K. Illendula · UNM’s Digital Repository (University of New Mexico) · 2000
Graph decomposition is an important and necessary operation when solving graph-theoretic problems on parallel computers, for instance, from computational fluid dynamics, mechanics, and astrophysics. In this paper, we design and analyze message-passing and shared-memory parallel algorithms that efficiently decompose a planar graph into a number of ears, known as the Ear Decomposition. This decomposition provides a general framework for solving graph problems efficiently in parallel. Our study includes both theoretical analysis and confirmation of the complexity cost using two leading parallel programming paradigms, namely, message-passing (MPI) and shared-memory (SMP) implementations. A catalog of both regular and irregular input graphs are provided to benchmark these algorithms in our empirical study. Keywords Parallel Algorithms, Symmetric Multiprocessors (SMP), Shared Memory, Message Passing Interface (MPI), Experimental Parallel Algorithmics. UNM Technical Report: EECE-TR-00-002...