Nearly optimal parallel algorithm for constructing depth first spanning trees in planar graphs

Xin He; Yaacov Yesha

doi:10.1137/0217028

Nearly optimal parallel algorithm for constructing depth first spanning trees in planar graphs

Xin He
, Yaacov Yesha

Department of Computer Science and Engineering

Ohio State University

Research output: Contribution to journal › Article › peer-review

19 Scopus citations

Abstract

This paper presents a parallel algorithm for constructing depth first spanning trees in planar graphs. The algorithm takes O(log²n) time with O(n) processors on a concurrent read concurrent write parallel random access machine (PRAM). The best previously known algorithm for the problem takes O(log³n) time with O(n⁴) processors on a PRAM. Our algorithm is within an O(log²n) factor of optimality.

Original language	English
Pages (from-to)	486-491
Number of pages	6
Journal	SIAM Journal on Computing
Volume	17
Issue number	3
DOIs	https://doi.org/10.1137/0217028
State	Published - 1988

Access to Document

10.1137/0217028

Cite this

@article{6e789a62a63147678a234afeff78c22f,

title = "Nearly optimal parallel algorithm for constructing depth first spanning trees in planar graphs",

abstract = "This paper presents a parallel algorithm for constructing depth first spanning trees in planar graphs. The algorithm takes O(log2n) time with O(n) processors on a concurrent read concurrent write parallel random access machine (PRAM). The best previously known algorithm for the problem takes O(log3n) time with O(n4) processors on a PRAM. Our algorithm is within an O(log2n) factor of optimality.",

author = "Xin He and Yaacov Yesha",

year = "1988",

doi = "10.1137/0217028",

language = "English",

volume = "17",

pages = "486--491",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "3",

}

TY - JOUR

T1 - Nearly optimal parallel algorithm for constructing depth first spanning trees in planar graphs

AU - He, Xin

AU - Yesha, Yaacov

PY - 1988

Y1 - 1988

N2 - This paper presents a parallel algorithm for constructing depth first spanning trees in planar graphs. The algorithm takes O(log2n) time with O(n) processors on a concurrent read concurrent write parallel random access machine (PRAM). The best previously known algorithm for the problem takes O(log3n) time with O(n4) processors on a PRAM. Our algorithm is within an O(log2n) factor of optimality.

AB - This paper presents a parallel algorithm for constructing depth first spanning trees in planar graphs. The algorithm takes O(log2n) time with O(n) processors on a concurrent read concurrent write parallel random access machine (PRAM). The best previously known algorithm for the problem takes O(log3n) time with O(n4) processors on a PRAM. Our algorithm is within an O(log2n) factor of optimality.

UR - https://www.scopus.com/pages/publications/0024019535

U2 - 10.1137/0217028

DO - 10.1137/0217028

M3 - Article

AN - SCOPUS:0024019535

SN - 0097-5397

VL - 17

SP - 486

EP - 491

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 3

ER -

Nearly optimal parallel algorithm for constructing depth first spanning trees in planar graphs

Abstract

Access to Document

Other files and links

Fingerprint

Cite this