Depth-first search in directed planar graphs, revisited

Eric Allender, Archit Chauhan, Samir Datta

Research output: Contribution to journalArticlepeer-review

Abstract

We present an algorithm for constructing a depth-first search tree in planar digraphs; the algorithm can be implemented in the complexity class AC1(UL∩co-UL), which is contained in AC2. Prior to this (for more than a quarter-century), the fastest uniform deterministic parallel algorithm for this problem had a runtime of O(log 10n) (corresponding to the complexity class AC10⊆NC11). We also consider the problem of computing depth-first search trees in other classes of graphs and obtain additional new upper bounds.

Original languageEnglish (US)
JournalActa Informatica
DOIs
StateAccepted/In press - 2022

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Depth-first search in directed planar graphs, revisited'. Together they form a unique fingerprint.

Cite this