47 Result(s)

Article

Minimum-Cost Flows in Unit-Capacity Networks

We 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 th...

Andrew V. Goldberg, Sagi Hed, Haim Kaplan, Robert E. Tarjan in Theory of Computing Systems (2017)

Reference Work Entry In depth

Hub Labeling (2-Hop Labeling)

Daniel Delling, Andrew V. Goldberg, Renato F. Werneck in Encyclopedia of Algorithms (2016)

Reference Work Entry In depth

Implementation Challenge for Shortest Paths

Camil Demetrescu, Andrew V. Goldberg, David S. Johnson in Encyclopedia of Algorithms (2016)

Article

An exact combinatorial algorithm for minimum graph bisection

We 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 b...

Daniel Delling, Daniel Fleischman, Andrew V. Goldberg… in Mathematical Programming (2015)

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...

Andrew V. Goldberg, Sagi Hed, Haim Kaplan, Pushmeet Kohli… in Algorithms - ESA 2015 (2015)

Chapter and Conference Paper

On the Complexity of Hub Labeling (Extended Abstract)

Hub Labeling (HL) is a data structure for distance oracles. Hierarchical HL (HHL) is a special type of HL, that received a lot of attention from a practical point of view. However, theoretical questions such as N...

Maxim Babenko, Andrew V. Goldberg… in Mathematical Foundations of Computer Scien… (2015)

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...

Daniel Delling, Andrew V. Goldberg, Ruslan Savchenko… in Experimental Algorithms (2014)

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...

Daniel Delling, Andrew V. Goldberg, Thomas Pajor… in Algorithms - ESA 2014 (2014)

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...

Andrew V. Goldberg in Experimental Algorithms (2013)

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...

Andrew V. Goldberg, Ilya Razenshteyn… in Mathematical Foundations of Computer Scien… (2013)

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...

Maxim Babenko, Andrew V. Goldberg, Anupam Gupta… in Automata, Languages, and Programming (2013)

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...

Daniel Delling, Andrew V. Goldberg, Renato F. Werneck in Experimental Algorithms (2013)

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...

Ittai Abraham, Daniel Delling, Andrew V. Goldberg… in Algorithms – ESA 2012 (2012)

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 ...

Ittai Abraham, Daniel Delling, Amos Fiat… in Automata, Languages and Programming (2011)

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...

Andrew V. Goldberg, Sagi Hed, Haim Kaplan, Robert E. Tarjan… in Algorithms – ESA 2011 (2011)

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...

Ittai Abraham, Daniel Delling, Andrew V. Goldberg… in Experimental Algorithms (2011)

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...

Daniel Delling, Andrew V. Goldberg, Thomas Pajor… in Experimental Algorithms (2011)

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...

Ittai Abraham, Daniel Delling, Andrew V. Goldberg… in Experimental Algorithms (2010)