
CS 860, Algorithms for Shortest Paths, Fall 2014






Papers to Present








Notes: Papers are listed by date so you can see what's new. Some of the papers will have been mentioned in class. Asterisks (to left) indicate most important/worthwhile papers.







Monday September 8






radix heap implementation of Dijkstra's algorithm








experiments on shortest path algorithms








a data structures paper, uses word RAM model





Wednesday September 10






not central to shortest paths, but interesting





Monday September 15







homotopic shortest path















2point queries















diameter and center






general technique. Used for diameter of simple polygon.













minimum link paths























L1 distances






Also other recent papers by the same authors.





curved obstacles











one more paper on Dijkstra






speedups for Dijkstra's algorithm





Wednesday September 17







shortest paths on polyhedral surfaces























3 dimensions






NPhardness of 3D shortest paths




careful version of approximation algorithm









weighted region and related problems



































Monday September 22







more papers on single source graph shortest paths










this paper and the previous one go together





Shihabur Rahman Chowdhury








all pairs shortest paths



























center and diameter


















a physics paper about the diameter of the www





planar graphs



















hierarchical graphs



















kth shortest paths















shortest paths in dynamic graphs


















a lower bound based on 3SUM




this paper goes with the one above  an algorithm for 3SUM





bicriteria shortest paths











Wednesday September 24







one more paper on dynamic graphs






Lap Chi Lau will be a prof here





spanners






spanners of general graphs





spanners of geometric graphs














allow Steiner points, approximate shortest paths





Monday October 6







Travelling Salesman Problem






















or look at later papers on this topic




watchman route for polygon with holes





routing































shortest path queries






survey paper. Don't present, just use as source.

