Algorithmic Aspects in Information and Management
5th International Conference, AAIM 2009, San Francisco, CA, USA, June 15-17, 2009. Proceedings
Page
%P
-
Article
Maximum skew-symmetric flows and matchings
The maximum integer skew-symmetric flow problem (MSFP) generalizes both the maximum flow and maximum matching problems. It was introduced by Tutte [28] in terms of self-conjugate flows in antisymmetrical digra...
-
Chapter and Conference Paper
Point-to-Point Shortest Path Algorithms with Preprocessing
This is a survey of some recent results on point-to-point shortest path algorithms. This classical optimization problem received a lot of attention lately and significant progress has been made. After an overv...
-
Chapter and Conference Paper
Better Landmarks Within Reach
We present significant improvements to a practical algorithm for the point-to-point shortest path problem on road networks that combines A* search, landmark-based lower bounds, and reach-based pruning. Through re...
-
Reference Work Entry In depth
Implementation Challenge for Shortest Paths
-
Chapter and Conference Paper
The Partial Augment–Relabel Algorithm for the Maximum Flow Problem
The maximum flow problem is a classical optimization problem with many applications. For a long time, HI-PR, an efficient implementation of the highest-label push-relabel algorithm, has been a benchmark due to...
-
Book and Conference Proceedings
-
Chapter and Conference Paper
Two-Level Push-Relabel Algorithm for the Maximum Flow Problem
We describe a two-level push-relabel algorithm for the maximum flow problem and compare it to the competing codes. The algorithm generalizes a practical algorithm for bipartite flows. Experiments show that the...
-
Chapter and Conference Paper
Alternative Routes in Road Networks
We 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 de...
-
Chapter and Conference Paper
VC-Dimension and Shortest Path Algorithms
We 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 ...
-
Chapter and Conference Paper
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...
-
Chapter and Conference Paper
A Hub-Based Labeling Algorithm for Shortest Paths in Road Networks
Abraham 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...
-
Chapter and Conference Paper
Customizable Route Planning
We 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 me...
-
Chapter and Conference Paper
Hierarchical Hub Labelings for Shortest Paths
We 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 pr...
-
Chapter and Conference Paper
The Hub Labeling Algorithm
Given a weighted graph, a distance oracle takes as an input a pair of vertices and returns the distance between them. The labeling approach to distance oracle design is to precompute a label for every vertex s...
-
Chapter and Conference Paper
Separating Hierarchical and General Hub Labelings
In the context of distance oracles, a labeling algorithm computes vertex labels during preprocessing. An s,t query computes the corresponding distance using the labels of s and t only, without looking at the inpu...
-
Chapter and Conference Paper
Algorithms for Hub Label Optimization
We 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 siz...
-
Chapter and Conference Paper
Hub Label Compression
The hub labels (HL) algorithm is the fastest known technique for computing driving times on road networks, but its practical applicability can be limited by high space requirements relative to the best competi...
-
Chapter and Conference Paper
Hub Labels: Theory and Practice
The 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...
-
Chapter and Conference Paper
Robust Distance Queries on Massive Networks
We present a versatile and scalable algorithm for computing exact distances on real-world networks with tens of millions of arcs in real time. Unlike existing approaches, preprocessing and queries are practica...
-
Chapter and Conference Paper
Faster and More Dynamic Maximum Flow by Incremental Breadth-First Search
We introduce the Excesses Incremental Breadth-First Search (Excesses IBFS) algorithm for maximum flow problems. We show that Excesses IBFS has the best overall practical performance on real-world instances, while...
