Zooming Through Euler Path: Supercharging with GPU

So, continuing where we left off: Walking the Euler Path: Intro Visualizing Graphs Walking the Euler Path: GPU for the Road Walking the Euler Path: PIN Cracking and DNA Sequencing For the Win And finally I ran the GPU-enabled algorithm for finding the Euler path. And the results: Generating euler graph: vertices = 10,485,760; avg … Continue reading Zooming Through Euler Path: Supercharging with GPU

Walking the Euler Path: PIN Cracking and DNA Sequencing

Continuing on to some cool applications of Eulerian paths. Intro Visualization GPU/CUDA Injection The goal of this little graph experiment remains exploration of accelerating Eulerian path finding on the GPU. This is the final introductory post. Eulerian Path Hierholzer algorithm works great. It's linear in the number of edges, so as fast as we can … Continue reading Walking the Euler Path: PIN Cracking and DNA Sequencing

Walking the Euler Path: GPU for the Road

Continuation of the previous posts: Intro Visualization GPU Digression I was going to talk about something else this week but figured I'd take advantage of the free-hand format and digress a bit. Continuing the travel metaphor and remembering Julius Cesar's "alea iacta", we'll talk about GPU algorithms, for which I invariably use my favorite Aela.CUDA … Continue reading Walking the Euler Path: GPU for the Road

Turnpike Problem (F#)

The Problem This is a problem for which no polynomial time solution exists, although a pseudo-polynomial (polynomial in the degree of the maximum element) does exist. In this paper, the algorithm proposed for the sum-function with full information is simple enough. For the original problem with the difference funcition, the algorithm is simple as well: … Continue reading Turnpike Problem (F#)