Efficient processing of which-edge questions on shortest path queries

Petrie Wong, Duncan Yung, Ming Hay Luk, Eric Lo, Man Lung Yiu, Kenny Q. Zhu

Research output: Journal article publicationConference articleAcademic researchpeer-review

Abstract

In this paper, we formulate a novel problem called Which-Edge question on shortest path queries. Specifically, this problem aims to find k edges that minimize the total distance for a given set of shortest path queries on a graph. This problem has important applications in logistics, urban planning, and network planning. We show the NP-hardness of the problem, as well as present efficient algorithms that compute highly accurate results in practice. Experimental evaluations are carried out on real datasets and results show that our algorithms are scalable and return high quality solutions.
Original languageEnglish
Pages (from-to)251-265
Number of pages15
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8421 LNCS
Issue numberPART 1
DOIs
Publication statusPublished - 1 Jan 2014
Event19th International Conference on Database Systems for Advanced Applications, DASFAA 2014 - Bali, Indonesia
Duration: 21 Apr 201424 Apr 2014

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this