Parallel Shortest-Path Queries in Planar Graphs

被引：1

作者：

Aleksandrov, Lyudmil ^{[1
]}

Chapuis, Guillaume ^{[2
]}

Djidjev, Hristo ^{[2
]}

机构：

[1] Bulgarian Acad Sci, IICT, G Bonchev Str 25-A, Sofia 1113, Bulgaria

[2] Los Alamos Natl Lab, Los Alamos, NM 87545 USA

来源：

PROCEEDINGS OF THE ACM WORKSHOP ON HIGH PERFORMANCE GRAPH PROCESSING (HPGP'16) | 2016年

关键词：

shortest path problems; graph algorithms; distance queries; distributed computing; graph partitioning; SMALL TREEWIDTH; ALGORITHMS; DIGRAPHS;

D O I：

10.1145/2915516.2915518

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

We develop several parallel algorithms for shortest distance queries in planar graphs that use graph partitioning in the preprocessing phase to precompute and store distances between selected pairs of vertices. In the query phase, given a pair of arbitrary vertices v and w, the stored information is used to find the distance between v and w fast. The algorithms are implemented and tested on a high performance cluster with upto 256 16-core CPUs and their performances are analyzed and compared.

引用

页码：9 / 16

页数：8

共 17 条

[1] Algorithms for Approximate Shortest Path Queries on Weighted Polyhedral Surfaces [J].

Aleksandrov, Lyudmil ;

Djidjev, Hristo N. ;

Guo, Hua ;

Maheshwari, Anil ;

Nussbaum, Doron ;

Sack, Joerg-Ruediger .

DISCRETE & COMPUTATIONAL GEOMETRY, 2010, 44 (04) :762-801

[2]

Bast H., 2015, CoRR

[3] Shortest-Path Queries in Planar Graphs on GPU-Accelerated Architectures [J].

Chapuis, Guillaume ;

Djidjev, Hristo .

LARGE-SCALE SCIENTIFIC COMPUTING, LSSC 2015, 2015, 9374 :53-60

[4] Shortest paths in digraphs of small treewidth. Part I: Sequential algorithms [J].

Chaudhuri, S ;

Zaroliagis, CD .

ALGORITHMICA, 2000, 27 (3-4) :212-226

[5] Shortest paths in digraphs of small treewidth. Part II: Optimal parallel algorithms [J].

Chaudhuri, S ;

Zaroliagis, CD .

THEORETICAL COMPUTER SCIENCE, 1998, 203 (02) :205-223

[6] OpenMP: An industry standard API for shared-memory programming [J].

Dagum, L ;

Menon, R .

IEEE COMPUTATIONAL SCIENCE & ENGINEERING, 1998, 5 (01) :46-55

[7]

Dawes B., Boost C++ Libraries

[8]

Dijkstra E.W., 1959, Numerische Mathematik, V1, P269, DOI 10.1007/BF01386390

[9]

Djidjev H. N., 2016, TECHNICAL REPORT

[10]

Djidjev HN, 1997, LECT NOTES COMPUT SC, V1197, P151

← 1 2 →