CS 860, Algorithms for Shortest Paths, Fall 2014


V Papers to Present
comments
(to be) presented by
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.
V Monday September 8
✽
* Faster algorithms for the shortest path problem
RK Ahuja, K Mehlhorn, J Orlin, RE Tarjan - Journal of the ACM (JACM), 1990
radix heap implementation of Dijkstra's algorithm
* Undirected single-source shortest paths with positive integer weights in linear time
M Thorup - Journal of the ACM (JACM)
* Shortest paths algorithms: Theory and experimental evaluation
BV Cherkassky, AV Goldberg, T Radzik - Mathematical programming, 1996
experiments on shortest path algorithms
✽
* Computing the shortest path: A* search meets graph theory
AV Goldberg, C Harrelson - Proceedings of the sixteenth annual ACM- …, 2005
André Linhares
* Trans-dichotomous algorithms for minimum spanning trees and shortest paths
ML Fredman, DE Willard - Journal of Computer and System Sciences, 1994
a data structures paper, uses word RAM model
V Wednesday September 10
*
A randomized algorithm for triangulating a simple polygon in linear time
NM Amato, MT Goodrich, EA Ramos - Discrete & Computational Geometry, 2001
not central to shortest paths, but interesting
V Monday September 15
V homotopic shortest path
* Computing minimum length paths of a given homotopy class
J Hershberger, J Snoeyink - Computational geometry, 1994
* Computing homotopic shortest paths efficiently
A Efrat, SG Kobourov, A Lubiw - Computational Geometry, 2006
improves above
V 2-point queries
* Two-point Euclidean shortest path queries in the plane
YJ Chiang, JSB Mitchell - Proceedings of the tenth annual ACM-SIAM …, 1999
* Shortest path queries in polygonal domains
H Guo, A Maheshwari, JR Sack - Algorithmic Aspects in Information and …, 2008
V diameter and center
✽
* Matrix searching with the shortest-path metric
J Hershberger, S Suri - SIAM Journal on Computing, 1997
general technique. Used for diameter of simple polygon.
* Computing the geodesic center of a simple polygon
R Pollack, M Sharir, G Rote - Discrete & Computational Geometry, 1989
✽
* The geodesic diameter of polygonal domains
SW Bae, M Korman, Y Okamoto - Discrete & Computational Geometry, 2013
V minimum link paths
✽
* Minimum-link paths among obstacles in the plane
JSB Mitchell, G Rote, G Woeginger - Algorithmica, 1992
* On the bit complexity of minimum link paths: superquadratic algorithms for problem solvable in linear time
S Kahan, J Snoeyink - Computational Geometry: Theory and …, 1999
real RAM too powerful
* Logarithmic-time link path queries in a simple polygon
EM Arkin, JSB Mitchell, S Suri - International Journal of …, 1995
* AnO (n logn) algorithm for computing the link center of a simple polygon
HN Djidjev, A Lingas, JR Sack - Discrete & Computational Geometry, 1992
V L1 distances
* L_1 Shortest Path Queries among Polygonal Obstacles in the Plane http://dx.doi.org/10.4230/LIPIcs.STACS.2013.293
Danny Z. Chen, Haitao Wang - STACS 2013
Also other recent papers by the same authors.
V curved obstacles
* Computing shortest paths among curved obstacles in the plane
DZ Chen, H Wang - … annual symposium on Symposuim on computational …, 2013
Hamideh Vosoghpour
V one more paper on Dijkstra
* Combining speed-up techniques for shortest-path computations
M Holzer, F Schulz, D Wagner, T Willhalm - Journal of Experimental …, 2005
speed-ups for Dijkstra's algorithm
V Wednesday September 17
V shortest paths on polyhedral surfaces
* The discrete geodesic problem
JSB Mitchell, DM Mount, CH Papadimitriou - SIAM Journal on Computing, 1987
continuous Dijkstra
* Fast exact and approximate geodesics on meshes
V Surazhsky, T Surazhsky, D Kirsanov… - ACM Transactions on …, 2005
more practical
Ryan Goldade
✽
* Shortest paths on a polyhedron, Part I: Computing shortest paths
J Chen, Y Han - International Journal of Computational Geometry & …, 1996
Anna Lubiw
* An optimal-time algorithm for shortest paths on a convex polytope in three dimensions
Y Schreiber, M Sharir - Twentieth Anniversary Volume:, 2009 - Springer
V 3 dimensions
* New lower bound techniques for robot motion planning problems
J Canny, J Reif - … of Computer Science, 1987., 28th Annual …, 1987
NP-hardness of 3D shortest paths
* Precision-sensitive Euclidean shortest path in 3-Space
J Sellen, J Choi, CK Yap - SIAM Journal on Computing, 2000
careful version of approximation algorithm
* An approximation algorithm for computing shortest paths in weighted 3-d domains
L Aleksandrov, H Djidjev, A Maheshwari… - Discrete & Computational …, 2013
V weighted region and related problems
* The weighted region problem: finding shortest paths through a weighted planar subdivision
JSB Mitchell, CH Papadimitriou - Journal of the ACM (JACM), 1991
* Determining approximate shortest paths on weighted polyhedral surfaces
L Aleksandrov, A Maheshwari, JR Sack - Journal of the ACM (JACM)
* On finding approximate optimal paths in weighted regions
Z Sun, JH Reif - Journal of Algorithms, 2006
* Trekking in the Alps without freezing or getting tired
M De Berg, M van Kreveld - Algorithmica, 1997
* Approximation algorithms for shortest descending paths in terrains
M Ahmed, S Das, S Lodha, A Lubiw… - … of Discrete Algorithms, 2010
* Shortest descending paths: Towards an exact algorithm
M Ahmed, A Lubiw - International Journal of Computational …, 2011
✽
* Approximate shortest descending paths
SW Cheng, J Jin - SIAM Journal on Computing, 2014
V Monday September 22
V more papers on single source graph shortest paths
* Sorting and searching on the word RAM
T Hagerup - STACS 98, 1998
* Improved shortest paths on the word RAM
T Hagerup - Automata, Languages and Programming, 2000
this paper and the previous one go together
* A simple shortest path algorithm with linear average time
AV Goldberg - Algorithms—ESA 2001
Shihabur Rahman Chowdhury
* A faster algorithm for the single source shortest path problem with few distinct positive lengths
JB Orlin, K Madduri, K Subramani… - … of Discrete Algorithms, 2010
V all pairs shortest paths
✽
* Randomized Speedup of the Bellman-Ford Algorithm.
MJ Bannister, D Eppstein - ANALCO, 2012
Philippe Demontigny
* All-pairs shortest paths with real weights in O (n 3/log n) time
TM Chan - Algorithmica, 2008
Timothy Chan
* Finding the hidden path: Time bounds for all-pairs shortest paths
DR Karger, D Koller, SJ Phillips - SIAM Journal on Computing, 1993
✽
* On the all-pairs-shortest-path problem in unweighted undirected graphs
R Seidel - Journal of computer and system sciences, 1995
Stephanie Lee
* All-pairs almost shortest paths
D Dor, S Halperin, U Zwick - SIAM Journal on Computing, 2000
V center and diameter
* Fast approximation algorithms for the diameter and radius of sparse graphs
L Roditty, V Vassilevska Williams - Proceedings of the forty-fifth annual …, 2013
* Diameter determination on restricted graph families
DG Corneil, FF Dragan, M Habib, C Paul - Discrete Applied Mathematics, 2001
about chordal graphs
* Center and diameter problems in plane triangulations and quadrangulations
V Chepoi, F Dragan, Y Vaxès - … of the thirteenth annual ACM-SIAM …, 2002
mix of graphs, geometry
* Scale-free characteristics of random networks: the topology of the world-wide web
AL Barabási, R Albert, H Jeong - Physica A: Statistical Mechanics and its …, 2000
a physics paper about the diameter of the www
V planar graphs
✽
* Faster shortest-path algorithms for planar graphs
MR Henzinger, P Klein, S Rao… - journal of computer and …, 1997
* Planar graphs, negative weight edges, shortest paths, and near linear time
J Fakcharoenphol, S Rao - Journal of Computer and System Sciences, 2006
Vijay Subramanya
* Compact oracles for reachability and approximate distances in planar digraphs
M Thorup - Journal of the ACM (JACM), 2004
V hierarchical graphs
* Exact routing in large road networks using contraction hierarchies
R Geisberger, P Sanders, D Schultes… - Transportation …, 2012
* Combining hierarchical and goal-directed speed-up techniques for dijkstra's algorithm
R Bauer, D Delling, P Sanders… - Journal of Experimental …, 2010
* Hierarchical hub labelings for shortest paths
I Abraham, D Delling, AV Goldberg, RF Werneck - Algorithms–ESA 2012
V kth shortest paths
✽
* Finding the k shortest paths
D Eppstein - SIAM Journal on computing, 1998
Nathan Lindzey
* Finding the k shortest simple paths: A new algorithm and its implementation
J Hershberger, M Maxel, S Suri - ACM Transactions on Algorithms ( …, 2007
V shortest paths in dynamic graphs
* Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs
V King - Foundations of Computer Science, 1999. 40th Annual …, 1999
✽
* A new approach to dynamic all pairs shortest paths
C Demetrescu, GF Italiano - Journal of the ACM (JACM), 2004
Khaled Ammar
* Experimental analysis of dynamic all pairs shortest path algorithms
C Demetrescu, GF Italiano - ACM Transactions on Algorithms (TALG), 2006
* Towards polynomial lower bounds for dynamic problems
M Patrascu - Proceedings of the 42nd ACM symposium on Theory of …, 2010
a lower bound based on 3SUM
* Threesomes, Degenerates, and Love Triangles
A Grønlund, S Pettie - arXiv preprint arXiv:1404.0799, 2014
this paper goes with the one above - an algorithm for 3SUM
V bicriteria shortest paths
* Resource constrained shortest paths
K Mehlhorn, M Ziegelmann - Algorithms-ESA 2000
Adam Domurad
V Wednesday September 24
V one more paper on dynamic graphs
* Efficient edge splitting-off algorithms maintaining all-pairs edge-connectivities
LC Lau, CK Yung - Integer Programming and Combinatorial Optimization, 2010
Lap Chi Lau will be a prof here
V spanners
* On sparse spanners of weighted graphs
I Althöfer, G Das, D Dobkin, D Joseph… - Discrete & Computational …, 1993
spanners of general graphs
V spanners of geometric graphs
✽
* Competitive routing in the half-θ 6-graph
P Bose, R Fagerberg, A van Renssen… - Proceedings of the …, 2012
Simon Pratt
* The stretch factor of the Delaunay triangulation is less than 1.998
G Xia - SIAM Journal on Computing, 2013
* Planar spanners and approximate shortest path queries among obstacles in the plane
S Arikati, DZ Chen, LP Chew, G Das, M Smid… - Algorithms—ESA'96
allow Steiner points, approximate shortest paths
V Monday October 6
V Travelling Salesman Problem
* Approximating graphic TSP by matchings
T Momke, O Svensson - Foundations of Computer Science ( …, 2011
* New inapproximability bounds for TSP
M Karpinski, M Lampis, R Schmied - Algorithms and Computation, 2013
* Eight-fifth approximation for the path TSP
A Sebő - Integer Programming and Combinatorial Optimization, 2013
* \ frac {13}{9}-Approximation for Graphic TSP
M Mucha - Theory of Computing Systems, 2012
Oliver Grant
* Approximation algorithms for TSP with neighborhoods in the plane
A DUMITRESCU, JSB MITCHELL - Journal of algorithms, 2003
or look at later papers on this topic
* Approximating watchman routes
JSB Mitchell - Proceedings of the Twenty-Fourth Annual ACM-SIAM …, 2013
watchman route for polygon with holes
V routing
* Routing with guaranteed delivery in ad hoc wireless networks
P Bose, P Morin, I Stojmenović, J Urrutia - Wireless networks, 2001
for unit disk graphs
* Online routing in triangulations
P Bose, P Morin - SIAM journal on computing, 2004
* Some results on greedy embeddings in metric spaces
T Leighton, A Moitra - Discrete & Computational Geometry, 2010
* Succinct greedy drawings do not always exist
P Angelini, G Di Battista, F Frati - Networks, 2012
* Competitive online routing in geometric graphs
P Bose, P Morin - Theoretical Computer Science, 2004
* Compact name-independent routing with minimum stretch
I Abraham, C Gavoille, D Malkhi, N Nisan… - ACM Transactions on …, 2008
routing tables
V shortest path queries
* Shortest-path queries in static networks
C Sommer - ACM Computing Surveys (CSUR), 2014
survey paper. Don't present, just use as source.