Abstract

Abstract: Given an undirected edge-weighted graph $G$ and a subset of vertices $S$ in it, the graph convex hull $CH^G_S$ of $S$ in $G$ is the set of vertices obtained by the process of initializing $CH^G_S$ to $S$ and iteratively adding until convergence all vertices on all shortest paths between all pairs of vertices in $CH^G_S$ of one iteration to constitute $CH^G_S$ of the next iteration. Computing the graph convex hull has applications in shortest-path computations, active learning, and in identifying geodesic cores in social networks, among others. Unfortunately, computing it exactly is prohibitively expensive on large graphs. In this paper, we present a FastMap-based algorithm for efficiently computing approximate graph convex hulls. FastMap is a graph embedding algorithm that embeds a given undirected edge-weighted graph into a Euclidean space in near-linear time such that the pairwise Euclidean distances between vertices approximate the shortest-path distances between them. Using FastMap's ability to facilitate geometric interpretations, our approach invokes the power of well-studied algorithms in Computational Geometry that efficiently compute the convex hull of a set of points in Euclidean space. Through experimental studies, we show that our approach not only is several orders of magnitude faster than the exact brute-force algorithm but also outperforms the state-of-the-art approximation algorithm, both in terms of generality and the quality of the solutions produced.

Download the paper in pdf.

Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.

This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.