Using FastMap to Solve Graph Problems in a Euclidean Space

July 2019

Using FastMap to Solve Graph Problems in a Euclidean Space

Authors:

Jiaoyang Li, Ariel Felner, Sven Koenig, and T. K. Satish Kumar

Abstract:

It is well known that many graph problems, like the Traveling Salesman Problem, are easier to solve in a Euclidean space. This motivates the idea of quickly preprocessing a given graph by embedding it in a Euclidean space to solve graph problems efficiently. In this paper, we study a nearlinear time algorithm, called FastMap, that embeds a given non-negative edge-weighted undirected graph in a Euclidean space and approximately preserves the pairwise shortest path distances between vertices. The Euclidean space can then be used either for heuristic guidance of A* (as suggested previously) or for geometric interpretations that facilitate the application of techniques from analytical geometry. We present a new variant of FastMap and compare it with the original variant theoretically and empirically. We demonstrate its usefulness for solving a path-finding and a multi-agent meeting problem.
@conference{Li-2019-131430,
author = {Jiaoyang Li And Ariel Felner And Sven Koenig And T. K. Satish Kumar},
title = {Using FastMap to Solve Graph Problems in a Euclidean Space},
booktitle = {Proceedings of 29th International Conference on Automated Planning and Scheduling (ICAPS '19)},
year = {2019},
month = {July},
pages = {273 - 278},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.