@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.; 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",

}