Graph algorithms on GPU
This is tangentially related to your question, but I've implemented a "recursive" backtracking algorithm for enumerating "self-avoiding walks" on a lattice (n.b.: the stack was simulated within the CUDA kernel, to avoid the overhead of creating local variables for a whole bunch of function calls). It's possible to do this efficiently, so I'm sure this can be adapted to a graph theoretical context. Here's a link to a seminar on the topic where I gave some general discussion about backtracking within the Single Instruction Multiple Data (SIMD) paradigm; it's a pdf of about 1MB in size http://bit.ly/9ForGS .
I don't claim to know about the wider literature on graph theoretical algorithms on GPUs, but hope the above helps a little.
(@TheMachineCharmer, thanks for the links.)
You will be interested in
Exploring the Limits of GPUs With Parallel Graph Algorithms
Accelerating large graph algorithms on the GPU using CUDA.