Export Citations
Publications
Save this search
Please login to be able to save your searches and receive alerts for new content matching your search criteria.
- article
Minimum-Cost Flows in Unit-Capacity Networks
Theory of Computing Systems, Volume 61, Issue 4•November 2017, pp 987-1010 • https://doi.org/10.1007/s00224-017-9776-7We consider combinatorial algorithms for the minimum-cost flow problem on networks with unit capacities, and special cases of the problem. Historically, researchers have developed special-purpose algorithms that exploit unit capacities. In contrast, for ...
- research-article
Highway Dimension and Provably Efficient Shortest Path Algorithms
Journal of the ACM, Volume 63, Issue 5•December 2016, Article No.: 41, pp 1-26 • https://doi.org/10.1145/2985473Computing driving directions has motivated many shortest path algorithms based on preprocessing. Given a graph, the preprocessing stage computes a modest amount of auxiliary data, which is then used to speed up online queries. In practice, the best ...
- research-article
Algorithms for Hub Label Optimization
ACM Transactions on Algorithms, Volume 13, Issue 1•January 2017, Article No.: 16, pp 1-17 • https://doi.org/10.1145/2996593We consider the hub label optimization problem, which arises in designing fast preprocessing-based shortest-path algorithms. We give O(log n)-approximation algorithms for the objectives of minimizing the maximum label size (ℓ∞-norm) and simultaneously ...
- research-article
Navigation made personal: inferring driving preferences from GPS traces
SIGSPATIAL '15: Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems•November 2015, Article No.: 31, pp 1-9• https://doi.org/10.1145/2820783.2820808All current navigation systems return efficient source-to-destination routes assuming a "one-size-fits-all" set of objectives, without addressing most personal preferences. Although they allow some customization (like "avoid highways" or "avoid tolls"), ...
- article
An exact combinatorial algorithm for minimum graph bisection
Mathematical Programming: Series A and B, Volume 153, Issue 2•November 2015, pp 417-458 • https://doi.org/10.1007/s10107-014-0811-zWe present a novel exact algorithm for the minimum graph bisection problem, whose goal is to partition a graph into two equally-sized cells while minimizing the number of edges between them. Our algorithm is based on the branch-and-bound framework and, ...
- research-article
Efficient maximum flow algorithms
Communications of the ACM, Volume 57, Issue 8•August 2014, pp 82-89 • https://doi.org/10.1145/2628036Though maximum flow algorithms have a long history, revolutionary progress is still being made.
- Article
Hub Labels: Theory and Practice
Proceedings of the 13th International Symposium on Experimental Algorithms - Volume 8504•June 2014, pp 259-270• https://doi.org/10.1007/978-3-319-07959-2_22The Hub Labeling algorithm (HL) is an exact shortest path algorithm with excellent query performance on some classes of problems. It precomputes some auxiliary information (stored as a label) for each vertex, and its query performance depends only on ...
- research-article
Scalable similarity estimation in social networks: closeness, node labels, and random edge lengths
COSN '13: Proceedings of the first ACM conference on Online social networks•October 2013, pp 131-142• https://doi.org/10.1145/2512938.2512944Similarity estimation between nodes based on structural properties of graphs is a basic building block used in the analysis of massive networks for diverse purposes such as link prediction, product recommendations, advertisement, collaborative filtering,...
- Article
Algorithms for hub label optimization
ICALP'13: Proceedings of the 40th international conference on Automata, Languages, and Programming - Volume Part I•July 2013, pp 69-80• https://doi.org/10.1007/978-3-642-39206-1_7We consider the problem of approximating optimal hub labelings in the context of labeling algorithms for the shortest path problem. A previous result was a O(logn) approximating for minimizing the total label size. We give an O(logn)-approximation ...
- research-article
Alternative routes in road networks
ACM Journal of Experimental Algorithmics, Volume 18•2013, Article No.: 1.3, pp 1.1-1.17 • https://doi.org/10.1145/2444016.2444019We study the problem of finding good alternative routes in road networks. We look for routes that are substantially different from the shortest path, have small stretch, and are locally optimal. We formally define the problem of finding alternative ...
- research-article
HLDB: location-based services in databases
SIGSPATIAL '12: Proceedings of the 20th International Conference on Advances in Geographic Information Systems•November 2012, pp 339-348• https://doi.org/10.1145/2424321.2424365This paper introduces HLDB, the first practical system that can answer exact spatial queries on continental road networks entirely within a database. HLDB is based on hub labels (HL), the fastest point-to-point algorithm for road networks, and its ...
- Article
Hierarchical hub labelings for shortest paths
ESA'12: Proceedings of the 20th Annual European conference on Algorithms•September 2012, pp 24-35• https://doi.org/10.1007/978-3-642-33090-2_4We study hierarchical hub labelings for computing shortest paths. Our new theoretical insights into the structure of hierarchical labels lead to faster preprocessing algorithms, making the labeling approach practical for a wider class of graphs. We also ...
- research-article
Exact combinatorial branch-and-bound for graph bisection
ALENEX '12: Proceedings of the Meeting on Algorithm Engineering & Expermiments•January 2012, pp 30-44We present a novel exact algorithm for the minimum graph bisection problem, whose goal is to partition a graph into two equally-sized cells while minimizing the number of edges between them. Our algorithm is based on the branch-and-bound framework and, ...
- Article
Maximum flows by incremental breadth-first search
Maximum flow and minimum s-t cut algorithms are used to solve several fundamental problems in computer vision. These problems have special structure, and standard techniques perform worse than the special-purpose Boykov-Kolmogorov (BK) algorithm. We ...
- Article
VC-dimension and shortest path algorithms
ICALP'11: Proceedings of the 38th international colloquim conference on Automata, languages and programming - Volume Part I•July 2011, pp 690-699We explore the relationship between VC-dimension and graph algorithm design. In particular, we show that set systems induced by sets of vertices on shortest paths have VC-dimension at most two. This allows us to use a result from learning theory to ...
- Article
Customizable route planning
SEA'11: Proceedings of the 10th international conference on Experimental algorithms•May 2011, pp 376-387We present an algorithm to compute shortest paths on continental road networks with arbitrary metrics (cost functions). The approach supports turn costs, enables real-time queries, and can incorporate a new metric in a few seconds--fast enough to ...
- Article
A hub-based labeling algorithm for shortest paths in road networks
SEA'11: Proceedings of the 10th international conference on Experimental algorithms•May 2011, pp 230-241Abraham et al. [SODA 2010] have recently presented a theoretical analysis of several practical point-to-point shortest path algorithms based on modeling road networks as graphs with low highway dimension. They also analyze a labeling algorithm. While no ...
- Article
Alternative routes in road networks
SEA'10: Proceedings of the 9th international conference on Experimental Algorithms•May 2010, pp 23-34• https://doi.org/10.1007/978-3-642-13193-6_3We study the problem of finding good alternative routes in road networks. We look for routes that are substantially different from the shortest path, have small stretch, and are locally optimal. We formally define the problem of finding alternative ...
- research-article
Highway dimension, shortest paths, and provably efficient algorithms
SODA '10: Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithms•January 2010, pp 782-793Computing driving directions has motivated many shortest path heuristics that answer queries on continental scale networks, with tens of millions of intersections, literally instantly, and with very low storage overhead. In this paper we complement the ...
- research-article
Shortest-path feasibility algorithms: An experimental evaluation
ACM Journal of Experimental Algorithmics, Volume 14•2009, Article No.: 7, pp 2.7-2.37 • https://doi.org/10.1145/1498698.1537602This is an experimental study of algorithms for the shortest-path feasibility problem: Given a directed weighted graph, find a negative cycle or present a short proof that none exists. We study previously known and new algorithms. Our testbed is more ...