ABSTRACT
We study the problem of efficiently computing journeys in timetable networks. Our algorithm optimally answers profile queries, computing all journeys given a time interval. Our study demonstrates that queries can be answered optimally on large country-scale timetable networks within several milliseconds and fast delay integration is possible. Previous work either had to drop optimality or only considered comparatively small timetable networks. Our technique is a combination of the Connection Scan Algorithm and multilevel overlay graphs.
Index Terms
- Connection scan accelerated
Recommendations
Connection Scan Algorithm
Special Issue ALENEX 2017We introduce the Connection Scan Algorithm (CSA) to efficiently answer queries to timetable information systems. The input consists, in the simplest setting, of a source position and a desired target position. The output consists of a sequence of ...
Cost-free scan: a low-overhead scan path design methodology
ICCAD '95: Proceedings of the 1995 IEEE/ACM international conference on Computer-aided designConventional scan design imposes considerable area and delay overhead by using larger scan flip-flops and additional scan wires without utilizing the functionality of the combinational logic. We propose a novel low-overhead scan design methodology, ...
On the Coverage of Delay Faults in Scan Designs with Multiple Scan Chains
ICCD '02: Proceedings of the 2002 IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD'02)The use of multiple scan chains for a scan design reduces the test application time by reducing the number of clock cycles required for a scan-in/scan-out operation. In this work, we show that the use of multiple scan chains also increases the fault ...
Comments