97 citations · 119 across the 6 of their papers we have counts for
6 papers
A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems
Yuanyuan Dong, Andrew V. Goldberg, Alexander Noe +3
Motivated by a real-world vehicle routing application, we consider the maximum-weight independent set problem: Given a node-weighted graph, find a set of independent (mutually nona…
New instances for maximum weight independent set from a vehicle routing application
Yuanyuan Dong, Andrew V. Goldberg, Alexander Noe +3
We present a set of new instances of the maximum weight independent set problem. These instances are derived from a real-world vehicle routing problem and are challenging to solve…
Route Planning in Transportation Networks
Hannah Bast, Daniel Delling, Andrew Goldberg +5
We survey recent advances in algorithms for route planning in transportation networks. For road networks, we show that one can compute driving directions in milliseconds or less ev…
On the Complexity of Hub Labeling
Maxim Babenko, Andrew V. Goldberg, Haim Kaplan +2
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,…
Separating Hierarchical and General Hub Labelings
Andrew V. Goldberg, Ilya Razenshteyn, Ruslan Savchenko
In the context of distance oracles, a labeling algorithm computes vertex labels during preprocessing. An query computes the corresponding distance from the labels of and…
Maximum Skew-Symmetric Flows and Matchings
Andrew V. Goldberg, Alexander V. Karzanov
The maximum integer skew-symmetric flow problem (MSFP) generalizes both the maximum flow and maximum matching problems. It was introduced by Tutte in terms of self-conjugate flows…