Research

DyDan, Universal Information Graphs

From Spring 2007 to Spring 2008, I worked on the Universal Information Graphs project (part of DyDan) with James Abello of DIMACS. I implemented a service for processing massive graphs to be visualized in ASK-GraphView.

Undergraduate Thesis

At Lafayette College, I completed an undergraduate thesis under the advisement of Prof. Jeffrey O. Pfaffmann.  Contributions include:

• A summary of cutting edge SSSP algorithms
• The first (known) implementation of Thorup’s algorithm
• Criteria for choosing a SSSP algorithm based upon domain knowledge

The full text (40 pages) of my thesis is available, as well as the source code (contains implementations of several SSSP algorithms – Goldberg, Thorup, Dijkstra – and data structures Radix Heaps) of my implementations.  The code is freely available in the public domain.

Internships at Sandia National Labs

Summers of 2005 and 2006, I interned at Sandia National Laboratories in Albuquerque, NM. At Sandia, my research included parallel implementations of graph algorithms. My advisor at Sandia was Dr. Jon Berry. I also worked with Kamesh Madduri of Georgia Tech.

Publications

Book Chapters

• Parallel Shortest Path Algorithms for Solving Large-Scale Instances
  K. Madduri, D.A. Bader, J.W. Berry, and J.R. Crobak
  C. Demetrescu, A.V. Goldberg, and D. Johnson, editors, Shortest Path Computations: Ninth DIMACS Challenge, AMS Press, 2009, to appear.
• Multithreaded Algorithms for Processing Massive Graphs
  K. Madduri, D.A. Bader, J.W. Berry, J.R. Crobak, and B.A. Hendrickson
  D.A. Bader, editor, Petascale Computing: Algorithms and Applications, CRC Press, 2007.

Conference Procedings

• Advanced Shortest Paths Algorithms on a Massively-Multithreaded Architecture
  J.R. Crobak, J. Berry, K. Madduri, and D.A. Bader
  Workshop on Multithreaded Architectures and Applications (MTAAP 2007), Long Beach, CA, March 26-30, 2007.
• An Experimental Study of A Parallel Shortest Path Algorithm for Solving Large-Scale Graph Instances
  K. Madduri, D.A. Bader, J.W. Berry, and J.R. Crobak
  Workshop on Algorithm Engineering and Experiments (ALENEX), New Orleans, LA, January 6, 2007.
• Parallel Shortest Path Algorithms for Solving Large-Scale Instances
  K. Madduri, D.A. Bader, J.W. Berry, and J.R. Crobak
  9th DIMACS Implementation Challenge — The Shortest Path Problem, DIMACS Center, Rutgers University, Piscataway, NJ, November 13-14, 2006.
• J.R. Crobak “Massively Multithreaded Shortest Path Algorithms: Applications at the Nanoscale,” Nanosciences, Engineering, and Computation Institute at Sandia, Summer 2006 Proceedings, Albuquerque, NM, August 2006.