Efficient parallel graph algorithms for multicore and multiprocessors

David A. Bader, Guojing Cong

Research output: Chapter in Book/Report/Conference proceedingChapter

5 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationHandbook of Parallel Computing
Subtitle of host publicationModels, Algorithms and Applications
PublisherCRC Press
ISBN (Electronic)9781420011296
ISBN (Print)9781584886235
StatePublished - Jan 1 2007
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Mathematics


Dive into the research topics of 'Efficient parallel graph algorithms for multicore and multiprocessors'. Together they form a unique fingerprint.

Cite this