An optimal parallel algorithm for planar cycle separators

Ming Yang Kao*, Shang Hua Teng, K. Toyama

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

We present an optimal parallel algorithm for computing a cycle separator of an n-vertex embedded planar undirected graph in O(log n) time on n/log n processors. As a consequence, we also obtain an improved parallel algorithm for constructing a depth-first search tree rooted at any given vertex in a connected planar undirected graph in O(log2n) time on 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.

Original languageEnglish (US)
Pages (from-to)398-408
Number of pages11
JournalAlgorithmica
Volume14
Issue number5
DOIs
StatePublished - Nov 1 1995

Keywords

  • Cycle separators
  • Depth-first search
  • Parallel algorithms
  • Planar graphs

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'An optimal parallel algorithm for planar cycle separators'. Together they form a unique fingerprint.

Cite this