Title:
生成方法、装置、及びプログラム
Document Type and Number:
Japanese Patent JP6520362
Kind Code:
B2
Abstract:
An apparatus generates, for each of vertices in a graph represented by the vertices and edges connecting the vertices, a first shortest-path tree rooted at a first root vertex equal to the each vertex, where the first shortest-path tree represents shortest paths from the first root vertex to vertices. The apparatus generates a vertex in the first shortest path tree whose distance from the first root vertex is a natural number of N, based on searching for one or more child vertices of a vertex within a second shortest-path tree rooted at a second root vertex adjacent to the first root vertex whose distance from the first root vertex is N−1, where the vertex for searching is included in both the first shortest-path tree and the second shortest-path tree.
Inventors:
Yasuo Yamane
Application Number:
JP2015094400A
Publication Date:
May 29, 2019
Filing Date:
May 01, 2015
Export Citation:
Assignee:
富士通株式会社
International Classes:
G06F16/00
Domestic Patent References:
| JP2011007713A | ||||
| JP2011103628A |
Other References:
Sebastian Knopp,Peter Sanders, Dominik Schultes,Frank Schulz, Dorothea Wagner,Computing Many-to-Many Shortest Paths UsingHighway Hierarchies,2007 Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments (ALENEX),米国,Society for Industrial and Applied Mathematics,2007年 1月 6日,http://www.siam.org/proceedings/alenex/2007/alx07_004knopp.pdf
Attorney, Agent or Firm:
Atsushi Nakajima
Kato Kazunori
Hiroshi Fukuda
Kato Kazunori
Hiroshi Fukuda