@inproceedings{df1493702bf54c5c894bca91fb6d61ec,
title = "Improved parallel depth-first search in undirected planar graphs",
abstract = "We present an improved parallel algorithm for constructing a depth-first search tree in a connected undirected planar graph. The algorithm runs in O(log2n) time with n/log n processors for an n-vertex graph. It hinges on the use of a new optimal algorithm for computing a cycle separator of an embedded planar graph in O(log n) time with n/log n processors. The best previous algorithms for computing depth-first search trees and cycle separators achieved the same time complexities, but with n processors. Our algorithms run on a parallel random access machine that permits concurrent reads and concurrent writes in its shared memory and allows an arbitrary processor to succeed in case of a write conflict.",
author = "Kao, {Ming Yang} and Teng, {Shang Hua} and Kentaro Toyama",
note = "Funding Information: *Departmenotf ComputeSrc ienceD, ukeU niversityD, urhamN, C 27706.Supporteidn part by NSF GrantC CR-9101385. tDepartmenotf MathematicsM, assachusetItnss tituteo f TechnologyC, ambridgeM, A 02139. SDepartmeonft C omputeSrc ienceY, ale UniversityN,e w HavenC, T 06520. Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1993.; 3rd Workshop on Algorithms and Data Structures, WADS 1993 ; Conference date: 11-08-1993 Through 13-08-1993",
year = "1993",
doi = "10.1007/3-540-57155-8_266",
language = "English (US)",
isbn = "9783540571551",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "409--420",
editor = "Frank Dehne and Jorg-Rudiger Sack and Nicola Santoro and Sue Whitesides",
booktitle = "Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings",
}