Back to Search
Start Over
Generating Node Coordinates for Shortest-Path Computations in Transportation Networks
- Publication Year :
- 2004
-
Abstract
- Speed-up techniques that exploit given node coordinates have proven useful for shortest-path computations in transportation networks and geographic information systems. To facilitate the use of such techniques when coordinates are missing from some, or even all, of the nodes in a network we generate artificial coordinates using methods from graph drawing. Experiments on a large set of German train timetables indicate that the speed-up achieved with coordinates from our drawings is close to that achieved with the true coordinates---and in some special cases even better.
- Subjects :
- shortest paths
Theoretical computer science
Geographic information system
travel planning
Exploit
Computer science
business.industry
Computation
Node (networking)
Theoretical Computer Science
graph drawing
Large set (Ramsey theory)
Graph drawing
transportation networks
Shortest path problem
ddc:004
business
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....ad4b671921131d706b384402616092b4