Efficient parallel graph algorithms for multicore and multiprocessors

Graph abstractions are used in many computationally challenging science and engineering problems. For instance, the minimum spanning tree (MST) problem finds a spanning tree of a connected graph G with the minimum sum of edge weights. MST is one of the most studied combinatorial problems with practical applications in VLSI layout, wireless communication, and distributed networks [67,87,95], recent problems in biology and medicine such as cancer detection [12,55,56,66], medical imaging [3], and proteomics [28,73], and national security and bioterrorism such as detecting the spread of toxins through populations in the case of biological/chemical warfare [13], and is often a key step in other graph problems [69,70,86,93]. Graph abstractions are also used in data mining, determining gene function, clustering in semantic webs, and security applications. For example, studies (e.g., References 21 and 59) have shown that certain activities are often suspicious not because of the characteristics of a single actor, but because of the interactions among a group of actors. Interactions are modeled through a graph abstraction where the entities are represented by vertices, and their interactions are the directed edges in the graph. This graph may contain billions of vertices with degrees ranging from small constants to thousands.