[FreecivDev] Re: Warmap
[Top] [All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
On Mon, 12 Aug 2002, Vasco Alexandre Da Silva Costa wrote:
> Regarding warmap speedups:
>
> If anyone feels up to implementing them, there are some algorithms which
> promise to solve the singlesource problem:
> <http://www.boost.org/libs/graph/doc/graph_theory_review.html>
>
> in linear time for undirected planar graphs:
> <http://mathworld.wolfram.com/PlanarGraph.html.html>.
>
> IIRC Dijkstra takes quadratic time in our implementation.
Yes I did some research on it previously, in particular read the papers by
Thorup and Goldberg that you are referring to below. Some of the
algorithms you mention are not applicable to our case which is nonplanar
graph with nonnegative (rather than strictly positive) weights.
Besides AFAIU the current implementation _is_ linear, at least in the
sense that Thorup's algorithm is linear (his discovery was that you can
pile nodes into a bucket list even though your weights are not integers 
this is already done in the current warmap). My own empirical discovery
was that if in our case you go for priority queue (log(n) time) rather
than for bucket list (constant time) you get a speedup: the bucket list
is too expensive to set up for the small $n$ we usually get.
G.
>
> === References:
>
> Faster shortestpath algorithms for planar graphs:
> <http://citeseer.nj.nec.com/henzinger94faster.html>
>
> Undirected single source shortest paths with positive integer weights in
> linear time:
> <http://citeseer.nj.nec.com/thorup99undirected.html>
>
> On RAM priority queues:
> <http://citeseer.nj.nec.com/thorup96ram.html>
>
>
> Andrew Goldberg's network optimization library:
> <http://www.avglab.com/andrew/soft.html>
>
> 
> Vasco Alexandre da Silva Costa @ Instituto Superior Tecnico, Lisboa
>
>
>
 [FreecivDev] Warmap, Vasco Alexandre Da Silva Costa, 2002/08/12
 [FreecivDev] Re: Warmap,
Gregory Berkolaiko <=

