Re: [boost] [gsoc2018] Dynamic Shortest Path Tree

Subject: Re: [boost] [gsoc2018] Dynamic Shortest Path Tree
From: David Bellot (david.bellot_at_[hidden])
Date: 2018-01-21 12:10:54

Hi everyone,

this could be a potential interesting GSoC
Anyone to mentor ?

Cheers,
David

On Wed, Jan 17, 2018 at 10:02 AM, A.I via Boost <boost_at_[hidden]>
wrote:

> Hi, I am Donghyuk Kim, a Ph.D. Student at Korea Advanced Institute of
> Science and Technology. I tried to contribute something last year but was
> not able to start the project for some reason. So I am about to re-try
> again this year.
>
> What I would like to contribute is a specific algorithm, "Dynamic Shortest
> Path Tree" which is simply, a dynamic version of Dijkstra's algorithm.
>
> It is a tree-based data structure to maintain single-source to all
> destination shortest paths and known to outperform Dijkstra or A* where the
> insertion and deletion of vertex/edge frequently occur.
>
> The concept of "Dynamic Shortest Path Computation" was originally
> introduced in
> [Fully Dynamic Algorithms for Maintaining Shortest Paths Trees] by D.
> Frigioni, et al.
> (http://dl.acm.org/citation.cfm?id=338900)
>
> I have already implemented a working prototype for my research, but unit
> test, coding style unification, and much more c++ style modifications are
> required for the general purpose.
>
> I hope someone finds it interesting and be a mentor on this journey.
>
> Thanks in advance.
>
> Best Regards,
> Donghyuk Kim
> a.i_at_[hidden]
>
> _____________________________________
> Sent from http://boost.2283326.n4.nabble.com
>
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/
> mailman/listinfo.cgi/boost
>