NDLI: Geometric containers for efficient shortest-path computation

Please wait, while we are loading the content...

Adaptive data structures for IP lookups

New heuristic and interactive approaches to 2D rectangular strip packing

Geometric containers for efficient shortest-path computation

Fast string sorting using order-preserving compression

Using random sampling to build approximate tries for efficient string sorting

A greedy approximation algorithm for the uniform metric labeling problem analyzed by a primal-dual technique

The datapath merging problem in reconfigurable systems: Complexity, dual bounds and heuristic evaluation

Implementing approximation algorithms for the single-source unsplittable flow problem

Improving the performance of multidimensional search using fingers

Combining speed-up techniques for shortest-path computations

Increased bit-parallelism for approximate and multiple string matching

In search for efficient heuristics for minimum-width graph layering with consideration of dummy nodes

Approximating interval coloring and max-coloring in chordal graphs

A Tabu search heuristic with efficient diversification strategies for the class/teacher timetabling problem

Geometric containers for efficient shortest-path computation

Content Provider	ACM Digital Library
Author	Wagner, Dorothea Willhalm, Thomas Zaroliagis, Christos
Copyright Year	2005
Abstract	A fundamental approach in finding efficiently best routes or optimal itineraries in traffic information systems is to reduce the search space (part of graph visited) of the most commonly used shortest path routine (Dijkstra's algorithm) on a suitably defined graph. We investigate reduction of the search space while simultaneously retaining data structures, created during a preprocessing phase, of size linear (i.e., optimal) to the size of the graph. We show that the search space of Dijkstra's algorithm can be significantly reduced by extracting geometric information from a given layout of the graph and by encapsulating precomputed shortest-path information in resulted geometric objects (containers). We present an extensive experimental study comparing the impact of different types of geometric containers using test data from real-world traffic networks. We also present new algorithms as well as an empirical study for the dynamic case of this problem, where edge weights are subject to change and the geometric containers have to be updated and show that our new methods are two to three times faster than recomputing everything from scratch. Finally, in an appendix, we discuss the software framework that we developed to realize the implementations of all of our variants of Dijkstra's algorithm. Such a framework is not trivial to achieve as our goal was to maintain a common code base that is, at the same time, small, efficient, and flexible, as we wanted to enhance and combine several variants in any possible way.
File Format	PDF
ISSN	10846654
e-ISSN	10846654
DOI	10.1145/1064546.1103378
Journal	Journal of Experimental Algorithmics (JEA)
Volume Number	10
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2005-12-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Data structures and algorithms Dijkstra's algorithm Geometric container Graph algorithms Shortest path Traffic network
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in