Cache-Oblivious Data Structures and Algorithms for Undirected Breadth-First Search and Shortest Paths

机译：无定向广度优先搜索和最短路径的高速缓存不可忽略的数据结构和算法

获取原文

获取原文并翻译 | 示例

页面导航

摘要
著录项
相似文献
相关主题

摘要

We present improved cache-oblivious data structures and algorithms for breadth-first search and the single-source shortest path problem on undirected graphs with non-negative edge weights. Our results removes the performance gap between the currently best cache-aware algorithms for these problems and their cache-oblivious counterparts. Our shortest-path algorithm relies on a new data structure, called bucket heap, which is the first cache-oblivious priority queue to efficiently support a weak DECREASEKEY operation.

机译：我们针对宽度优先搜索和具有非负边权重的无向图上的单源最短路径问题，提出了改进的，可忽略缓存的数据结构和算法。我们的结果消除了当前针对这些问题的最佳高速缓存感知算法和其高速缓存无关的算法之间的性能差距。我们的最短路径算法依赖于称为“桶堆”的新数据结构，这是第一个可有效支持弱DECREASEKEY操作的缓存忽略优先级队列。

著录项

来源
《Scandinavian Workshop on Algorithm Theory(SWAT 2004); 20040708-20040710; Humlebaek; DK》|2004年|P.480-492|共13页
会议地点 Humlebaek(DK);Humlebaek(DK)
作者
Gerth Stolting Brodal; Rolf Fagerberg; Ulrich Meyer; Norbert Zeh;
展开▼
作者单位

BRICS, Department of Computer Science, University of Aarhus, DK-8000 Arhus C, Denmark;

展开▼
会议组织
原文格式 PDF
正文语种 eng
中图分类计算技术、计算机技术;
关键词

相似文献

外文文献
中文文献
专利

1. A fewest-turn-and-shortest path algorithm based on breadth-first search [J] . Yan Zhou, Weisheng Wang, Di He, Geo-spatial information science . 2014,第4期

机译：基于广度优先搜索的最少转弯和最短路径算法
2. A fewest-turn-and-shortest path algorithm based on breadth-first search [J] . Yan ZHOU, Weisheng WANG, Di HE, 地球空间信息科学学报（英文版） . 2014,第004期

机译：基于广度优先搜索的最少转弯和最短路径算法
3. An algorithm for finding shortest paths in undirected graphs with using the nearest neighbor search technique [J] . Kazuaki Yamaguchi, Yohei Iwami, Sumio Masuda 電子情報通信学会技術研究報告. コンピュテ-ション. Theoretical Foundations of Computing . 2001,第5期

机译：使用最近邻南搜索技术找到无向图中的最短路径的算法
4. Cache-Oblivious Data Structures and Algorithms for Undirected Breadth-First Search and Shortest Paths [C] . Gerth Stolting Brodal, Rolf Fagerberg, Ulrich Meyer, Scandinavian Workshop on Algorithm Theory . 2004

机译：缓存令人沮丧的数据结构和算法，无向第一搜索和最短路径
5. Space efficient string search algorithms and data structures. [D] . Deoghare, Pratik. 2015

机译：空间高效的字符串搜索算法和数据结构。
6. Algorithm for shortest path search in Geographic Information Systems by using reduced graphs [O] . Rafael Rodríguez-Puente, Manuel S Lazo-Cortés -1

机译：利用精简图进行地理信息系统最短路径搜索的算法
7. Cache-Oblivious Data Structures and Algorithms for Undirected Breadth-First Search and Shortest Paths [O] . Copyright C, Gerth Stølting Brodal, Rolf Fagerberg, 2004

机译：无定向广度优先搜索和最短路径的高速缓存数据结构和算法

Cache-Oblivious Data Structures and Algorithms for Undirected Breadth-First Search and Shortest Paths

摘要

著录项

相似文献

相关主题

期刊订阅