Parallel edge scan for single-source earliest-arrival in temporal graphs
US10360263B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jul 25, 2017 |
| Grant date | Jul 23, 2019 |
| Priority date | — |
| Expiry date | Oct 12, 2037 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06Q10/06
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Methods, systems, and computer-readable storage media for receiving data representative of the temporal graph, the data representing vertices, edges between vertices, and temporal features, determining a set of earliest-arrival dependencies, each earliest arrival dependency including an earliest feasible edge between vertices from a list of edges of the temporal graph, providing data representative of an edge-scan-dependency graph (ESD-graph) based on the data representative of the temporal graph, and the set of earliest-arrival dependencies, the ESD-graph including vertices representing edges of the temporal graph, and edges representing earliest-arrival dependencies between vertices, providing data representative of a level-assigned ESD-graph including a level assigned to each vertex of the ESD-graph, and determining earliest-arrival times between a source vertex, and each vertex of the temporal graph by executing a parallel edge scan of the level-assigned ESD-graph.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.