Publications

Refereed Publications

## 2014

- Daniel Delling, Andrew V. Goldberg, Ruslan Savchenko, and Renato F.Werneck, Hub Labels: Theory and Practice, in
*Proceedings of the 13th International Symposium on Experimental Algorithms (SEA'14)*, Springer, June 2014 - Daniel Delling, Moritz Kobitzsch, and Renato F. Werneck, Customizing Driving Directions with GPUs, in
*Proceedings of the 20th International Conference on Parallel Processing (Euro-Par 2014)*, Springer, 2014

## 2013

- Daniel Delling, Andrew V. Goldberg, Andreas Nowatzyk, and Renato F. Werneck, PHAST: Hardware-accelerated shortest path trees, in
*Journal of Parallel and Distributed Computing*, Elsevier, 2013 - Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck, Alternative Routes in Road Networks, in
*ACM Journal of Experimental Algorithmics*, vol. 18, no. 1, pp. 1–17, ACM, 2013 - Daniel Delling, Julian Dibbelt, Thomas Pajor, Dorothea Wagner, and Renato F. Werneck, Computing Multimodal Journeys in Practice, in
*Proceedings of the 12th International Symposium on Experimental Algorithms (SEA'13)*, Springer, 2013 - Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck, Hub Label Compression, in
*Proceedings of the 12th International Symposium on Experimental Algorithms (SEA'13)*, Springer Verlag, 2013 - Edith Cohen, Daniel Delling, Fabian Fuchs, Andrew V. Goldberg, Moises Goldszmidt, and Renato F. Werneck, Scalable Similarity Estimation in Social Networks: Closeness, Node Labels, and Random Edge Lengths, in
*Proceedings of the ACM Conference on Online Social Networks (COSN'13)*, ACM, 2013 - Daniel Delling and Renato Werneck, Faster Customization of Road Networks, in
*Proceedings of the 12th International Symposium on Experimental Algorithms (SEA'13)*, Springer, 2013

## 2012

- Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck, HLDB: Location-Based Services in Databases, in
*SIGSPATIAL GIS*, ACM, November 2012 - Diogo V. Andrade, Mauricio G. C. Resende, and Renato F. Werneck, Fast Local Search for the Maximum Independent Set Problem, in
*Journal of Heuristics*, vol. 18, no. 4, pp. 525-547, Springer, August 2012 - Eduardo Uchoa and Renato F. Werneck, Fast Local Search for the Steiner Problem in Graphs, in
*ACM Journal of Experimental Algorithmics*, vol. 17, no. 1, pp. 2.2, ACM, July 2012 - Daniel Delling, Andrew V. Goldberg, Ilya Razenshteyn, and Renato F. Werneck, Exact Combinatorial Branch-and-Bound for Graph Bisection, in
*Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX'12)*, Society for Industrial and Applied Mathematics, 2012 - Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck, Hierarchical Hub Labelings for Shortest Paths, in
*Proceedings of the 20th Annual European Symposium on Algorithms (ESA'12)*, Springer, 2012 - Daniel Delling, Thomas Pajor, and Renato F. Werneck, Round-Based Public Transit Routing, in
*Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX'12)*, Society for Industrial and Applied Mathematics, 2012 - Daniel Delling, Moritz Kobitzsch, Dennis Luxen, and Renato F. Werneck, Robust Mobile Route Planning with Limited Connectivity, in
*Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX'12)*, Society for Industrial and Applied Mathematics, 2012 - Daniel Delling and Renato F. Werneck, Better Bounds for Graph Bisection, in
*Proceedings of the 20th Annual European Symposium on Algorithms (ESA'12)*, Springer, 2012

## 2011

- Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck, A Hub-Based Labeling Algorithm for Shortest Paths on Road Networks, in
*Proceedings of the 10th International Symposium on Experimental Algorithms (SEA'11)*, Springer Verlag, May 2011 - Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck, Customizable Route Planning, in
*Proceedings of the 10th International Symposium on Experimental Algorithms (SEA'11)*, Springer Verlag, May 2011 - Loukas Georgiadis, Haim Kaplan, Nira Shafrir, Robert E. Tarjan, and Renato F. Werneck, Data Structures for Mergeable Trees, in
*ACM Transaction on Algorithms*, vol. 7, no. 2, pp. 14:1-14:30, ACM, March 2011 - Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck, Faster Batched Shortest Paths in Road Networks, in
*Proceedings of the 11th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'11)*, OpenAccess Series in Informatics, 2011 - Daniel Delling, Andrew V. Goldberg, Ilya Razenshteyn, and Renato F. Werneck, Graph Partitioning with Natural Cuts, in
*25th International Parallel and Distributed Processing Symposium (IPDPS'11)*, IEEE, 2011 - D. Delling, A.V. Goldberg, and R.F. Werneck, Shortest Paths in Road Networks: From Practice to Theory and Back, in
*Information Technology*, vol. 53, no. 6, pp. 294-301, 2011 - Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck, VC-Dimension and Shortest Path Algorithms, in
*Proc. ICALP 2011*, Springer Verlag, 2011 - Mihai Budiu, Daniel Delling, and Renato F. Werneck, DryadOpt: Branch-and-Bound on Distributed Data-Parallel Execution Engines, in
*25th International Parallel and Distributed Processing Symposium (IPDPS'11)*, IEEE, 2011 - A. V. Goldberg, S. Hed, H. Kaplan, R. E. Tarjan, and R. F. Werneck, Maximum Flows by Incremental Breadth-First Search, in
*19th European Symposium on Algorithms (ESA 2011)*, Springer Verlag, 2011 - Daniel Delling, Andrew V. Goldberg, Andreas Nowatzyk, and Renato F. Werneck, PHAST: Hardware-Accelerated Shortest Path Trees, in
*25th International Parallel and Distributed Processing Symposium (IPDPS'11)*, IEEE, 2011

## 2010

- Ittai Abraham, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck, Highway Dimension, Shortest Paths, and Provably Efficient Algorithms, in
*Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA10)*, Society for Industrial and Applied Mathematics, 2010 - Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck, Alternative Routes in Road Networks, in
*Proc. 9th International Symposium on Experimental Algorithms (SEA)*, Springer Verlag, 2010 - Eduardo Uchoa and Renato F. Werneck, Fast Local Search for Steiner Trees in Graphs, in
*Proceedings of the 12th Workshop on Algorithm Engineering and Experiments (ALENEX)*, Society for Industrial and Applied Mathematics, 2010

## 2009

- Dahlia Malkhi, Siddhartha Sen, Kunal Talwar, Renato Werneck, and Udi Wieder, Virtual Ring Routing Trends, in
*DISC 2009*, Springer Verlag, 23 September 2009 - A.V. Goldberg, H. Kaplan, and R.F. Werneck, Reach for A*: Shortest Path Algorithms with Preprocessing, in The Shortest Path Problem: Ninth DIMACS Implementation Challenge, pp. 93–140, AMS, 2009
- L. Georgiadis, A.V. Goldberg, R.E. Tarjan, and R.F. Werneck, An Experimental Study of Minimum Mean Cycle Algorithms, in
*Proc. 6th International Workshop on Algorithm Engineering and Experiments*, SIAM, 2009 - Robert E. Tarjan and Renato F. Werneck, Dynamic trees in practice , in
*ACM Journal of Experimental Algorithmics*, vol. 14, no. 4, pp. 4.5:1-4.5:21, Association for Computing Machinery, Inc., 2009 - Boris V. Cherkassky, Loukas Georgiadis, Andrew V. Goldberg, Robert E. Tarjan, and Renato F. Werneck, Shortest-Path Feasibility Algorithms: An Experimental Evaluation, in
*ACM Journal of Experimental Algorithmics*, vol. 14, no. 2, pp. 2.7:1-2.7:37, Association for Computing Machinery, Inc., 2009

## 2008

- Diogo V. Andrade, Mauricio G. C. Resende, and Renato F. Werneck, Fast Local Search for the Maximum Independent Set Problem, in
*International Workshop on Experimental Algorithms (WEA)*, Springer, Provincetown, MA, May 2008 - B.V. Cherkassky, L. Georgiadis, A.V. Goldberg, R.E. Tarjan, and Renato F. Werneck, Shortest Path Feasibility Algorithms: an Experimental Evaluation, in
*Proc. 6th International Workshop on Algorithm Engineering and Experiments*, SIAM, 2008

## 2007

- Andrew V. Goldberg, Haim Kaplan, and Renato F. Werneck, Better Landmarks within Reach, in
*Workshop on Experimental Algorithms (WEA)*, Rome, Italy, June 2007 - Robert E. Tarjan and Renato F. Werneck, Dynamic Trees in Practice, in
*International Workshop on Experimental Algorithms (WEA)*, Springer, Rome, Italy, June 2007

## 2006

- Ricardo Fukasawa, Humberto Longo, Jens Lysgaard, Marcus Poggi de Aragão, Marcelo Reis, Eduardo Uchoa, and Renato F. Werneck, Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem, in
*Mathematical Programming*, vol. 106, no. 3, pp. 491–511, Springer-Verlag, May 2006 - A.V. Goldberg, Haim Kaplan, and Renato F. Werneck, Reach for A*: Efficient Point-to-Point Shortest Path Algorithms, in
*SIAM Workshop on Algorithms Engineering and Experimentation (ALENEX 06)*, Society for Industrial and Applied Mathematics, Miami, FL, January 2006 - Loukas Georgiadis, Robert E. Tarjan, and Renato F. Werneck, Finding Dominators in Practice, in
*Journal of Graph Algorithms and Applications*, vol. 10, no. 1, pp. 69-94, 2006 - Mauricio G. C. Resende and Renato F. Werneck, A hybrid multistart heuristic for the uncapacitated facility location problem, in
*European Journal of Operational Research*, vol. 174, no. 1, pp. 54-68, Elsevier , 2006 - Robert E. Tarjan, Renato F. Werneck, and Loukas Georgiadis, Design of Data Structures for Mergeable Trees, in
*Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*, Society for Industrial and Applied Mathematics, January 2006

## 2005

- Robert E. Tarjan and Renato F. Werneck, Self-Adjusting Top Trees, in
*Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*, 2005 - A. V. Goldberg and R. Werneck, Computing Point-to-Point Shortest Paths from External Memory, in
*SIAM Workshop on Algorithms Engineering and Experimentation (ALENEX '05)*, Vancouver, Canada, 2005

## 2004

- Mauricio G. C. Resende and Renato F. Werneck, A hybrid heuristic for the p-median problem, in
*Journal of Heuristics*, vol. 10, no. 1, pp. 59–88, 2004

## 2003

- Mauricio G. C. Resende and Renato F. Werneck, On the implementation of a swap-based local search procedure for the p-median problem, in
*Proceedings of the 5th Workshop on Algorithm Engineering and Experiments (ALENEX)*, SIAM, 2003

## 2002

- M. Poggi de Aragão and Renato F. Werneck, On the Implementation of MST-based heuristics for the Steiner problem in graphs, in
*Proceedings of the Fourth International Workshop on Algorithm Engineering and Experiments (ALENEX'02)*, Springer-Verlag, 2002 - Celso C. Ribeiro, Eduardo Uchoa, and Renato F. Werneck, A hybrid GRASP with perturbations for the Steiner problem in graphs, in
*INFORMS Journal on Computing*, vol. 14, no. 3, pp. 228–246, 2002

## 2001

- M. Poggi de Aragão, Eduardo Uchoa, and Renato F. Werneck, Dual Heuristics on the Exact Solution of Large Steiner Problems, in
*Proceedings of the Brazilian Symposium on Graphs, Algoritms and Combinatorics*, Fortaleza, Brazil, 2001 - I. Rosseti, M. Poggi de Aragão, Celso C. Ribeiro, Eduardo Uchoa, and Renato F. Werneck, New benchmark instances for the Steiner problem in graphs, in
*Extended Abstracts of the 4th Metaheuristics International Conference*, Porto, Portugal, 2001 - M. Poggi de Aragão, Celso C. Ribeiro, Eduardo Uchoa, and Renato F. Werneck, Hybrid Local Search for the Steiner problem in graphs, in
*Extended Abstracts of the 4th Metaheuristics International Conference*, Porto, Portugal, 2001

## 2000

- Celso C. Ribeiro, Eduardo Uchoa, and Renato F. Werneck, A hybrid GRASP with perturbations and adaptive path-relinking for the Steiner problem in graphs, in
*Proceedings of the Workshop on Algorithm Engineering as a New Paradigm*, 2000 - Renato F. Werneck and J. C. Setubal, Finding Minimum Congestion Spanning Trees, in
*ACM Journal of Experimental Algorithmics*, vol. 5, 2000

## 1999

- João Carlos Setubal, Arlindo F. Conceição, and Renato F. Werneck, Finding Minimum Congestion Spanning Trees, in
*Proceedings of the Third Workshop on Algorithm Engineering (WAE'99)*, Springer Verlag, 1999

Other Publications

- Edith Cohen, Daniel Delling, Thomas Pajor, and Renato F. Werneck, Computing Classic Closeness Centrality, at Scale, no. MSR-TR-2014-71, 29 August 2014
- Edith Cohen, Daniel Delling, Thomas Pajor, and Renato Werneck, Sketch-based Influence Maximization and Computation: Scaling up with Guarantees, no. MSR-TR-2014-110, August 2014
- Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck, Robust Exact Distance Queries on Massive Networks, no. MSR-TR-2014-12, July 2014
- Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato Werneck, Route Planning in Transportation Networks, no. MSR-TR-2014-4, January 2014
- Daniel Delling and Renato Werneck, Customizable Point-of-Interest Queries in Road Networks, no. MSR-TR-2013-90, September 2013
- Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck, Highway Dimension and Provably Efficient Shortest Path Algorithms, no. MSR-TR-2013-91, September 2013
- Daniel Delling, Daniel Fleischman, Andrew V. Goldberg, Ilya Razenshteyn, and Renato F. Werneck, An Exact Combinatorial Algorithm for Minimum Graph Bisection, September 2013
- Daniel Delling, Andrew Goldberg, Thomas Pajor, and Renato Werneck, Customizable Route Planning in Road Networks, 2013
- Daniel Delling and Renato Werneck, Better Bounds for Graph Bisection, no. MSR-TR-2012-69, July 2012
- Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck, HLDB: Location-Based Services in Databases, no. MSR-TR-2012-59, June 2012