PARALLEL SEARCH ALGORITHMS FOR TREES AND GRAPHS

被引：0

作者：

CHAUDHURI, P ^{[1
]}

机构：

[1] UNIV NEW S WALES,SCH COMP SCI & ENGN,KENSINGTON,NSW 2033,AUSTRALIA

来源：

AUSTRALIAN COMPUTER JOURNAL | 1992年 / 24卷 / 02期

关键词：

PARALLEL ALGORITHMS; GRAPH THEORY; BINARY TREE; TREE TRAVERSAL; DEPTH-1ST SEARCH; BREADTH-1ST SEARCH; BREADTH-DEPTH SEARCH; PRAM MODEL; TIME COMPLEXITY;

D O I：

暂无

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

Tree and graph searching are of fundamental importance, since they form the basis for solving a wide range of other graph theory problems. Parallel algorithms developed for different types of tree and graph searching problems are mainly based on shared memory model of the single-instruction stream, multiple-data stream computer. This computational model may be viewed as a parallel variant of the standard Random Access Machine (RAM) model of sequential computation and is commonly known as parallel-RAM or PRAM in the literature. This paper aims in reviewing the algorithms for tree and graph searching problems on various PRAM models.

引用

页码：61 / 69

页数：9

共 50 条

[21] Parallel algorithms for Hamiltonian problems on quasi-threshold graphs [J].

Nikolopoulos, SD .

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2004, 64 (01) :48-67

[22] Improving Algorithms for Searching for Trees of Directed Graphs of Electrical Power Systems [J].

L. N. Gumilyov Eurasian National University, Astana, Kazakhstan ;

不详 .

Power Technol. Eng., 2 (349-355) :349-355

[23] Fringe analysis of synchronized parallel algorithms on 2-3 trees [J].

BaezaYates, R ;

Gabarró, J ;

Messeguer, X .

RANDOMIZATION AND APPROXIMATION TECHNIQUES IN COMPUTER SCIENCE, 1998, 1518 :131-144

[24] OPTIMAL PARALLEL ALGORITHMS FOR MULTIPLE UPDATES OF MINIMUM SPANNING-TREES [J].

PAWAGI, S ;

KASER, O .

ALGORITHMICA, 1993, 9 (04) :357-381

[25] PARALLEL ALGORITHMS FOR NEAREST NEIGHBOR SEARCH PROBLEMS IN HIGH DIMENSIONS [J].

Xiao, Bo ;

Biros, George .

SIAM JOURNAL ON SCIENTIFIC COMPUTING, 2016, 38 (05) :S667-S699

[26] Optimal sequential and parallel algorithms to compute a Steiner tree on permutation graphs [J].

Mondal, S ;

Pal, M ;

Pal, TK .

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2003, 80 (08) :937-943

[27] IMPROVED PROCESSOR BOUNDS FOR PARALLEL ALGORITHMS FOR WEIGHTED DIRECTED-GRAPHS [J].

AMATO, N .

INFORMATION PROCESSING LETTERS, 1993, 45 (03) :147-152

[28] Parallel algorithms for finding the center of interval and circular-arc graphs [J].

Hsu, FR ;

Shan, MK .

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2003, E86A (10) :2704-2709

[29] Some optimal parallel algorithms on interval and circular-arc graphs [J].

Hsu, FR ;

Shan, MK ;

Chao, HS ;

Lee, RCT .

JOURNAL OF INFORMATION SCIENCE AND ENGINEERING, 2005, 21 (03) :627-642

[30] Sequential and parallel algorithms on compactly represented chordal and strongly chordal graphs [J].

Dahlhaus, E .

STACS 97 - 14TH ANNUAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE, 1997, 1200 :487-498

← 1 2 3 4 5 →