Email RIS file
Bookmark
Report an Issue

A Graph Search Heuristic for Shortest Distance Paths [electronic resource].

Published
Washington, D.C. : United States. Dept. of Energy, 2005.
Oak Ridge, Tenn. : Distributed by the Office of Scientific and Technical Information, U.S. Dept. of Energy.
Physical Description
PDF-file: 8 pages; size: 0.2 Mbytes
Additional Creators
Lawrence Berkeley National Laboratory, United States. Department of Energy, and United States. Department of Energy. Office of Scientific and Technical Information
Access Online

Availability

I Want It
I Want It

Finding items...

Restrictions on Access
Free-to-read Unrestricted online access
Summary
This paper presents a heuristic for guiding A* search for finding the shortest distance path between two vertices in a connected, undirected, and explicitly stored graph. The heuristic requires a small amount of data to be stored at each vertex. The heuristic has application to quickly detecting relationships between two vertices in a large information or knowledge network. We compare the performance of this heuristic with breadth-first search on graphs with various topological properties. The results show that one or more orders of magnitude improvement in the number of vertices expanded is possible for large graphs, including Poisson random graphs.
Report Numbers
E 1.99:ucrl-conf-210878
ucrl-conf-210878
Subject(s)
Other Subject(s)
Note
Published through SciTech Connect.
03/24/2005.
"ucrl-conf-210878"
Presented at: AAAI-05: The Twentieth National Conference on Artificial Intelligence, Pittsburgh, PA, United States, Jul 09 - Jul 13, 2005.
Chow, E.
Funding Information
W-7405-ENG-48
View MARC record | catkey: 14345382