Depth-first search in directed planar graphs, revisited

Eric Allender; Archit Chauhan; Samir Datta

doi:10.1007/s00236-022-00425-1

Depth-first search in directed planar graphs, revisited

Eric Allender, Archit Chauhan, Samir Datta

School of Arts and Sciences, Computer Science

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

4 Scopus citations

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 ¹⁰n) (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 language	English (US)
Pages (from-to)	289-319
Number of pages	31
Journal	Acta Informatica
Volume	59
Issue number	4
DOIs	https://doi.org/10.1007/s00236-022-00425-1
State	Published - Aug 2022

All Science Journal Classification (ASJC) codes

Software
Information Systems
Computer Networks and Communications

Access to Document

10.1007/s00236-022-00425-1

Cite this

@article{f090248000164511974a3e14a44ece02,

title = "Depth-first search in directed planar graphs, revisited",

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

author = "Eric Allender and Archit Chauhan and Samir Datta",

note = "Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature.",

year = "2022",

month = aug,

doi = "10.1007/s00236-022-00425-1",

language = "English (US)",

volume = "59",

pages = "289--319",

journal = "Acta Informatica",

issn = "0001-5903",

publisher = "Springer New York",

number = "4",

}

TY - JOUR

T1 - Depth-first search in directed planar graphs, revisited

AU - Allender, Eric

AU - Chauhan, Archit

AU - Datta, Samir

PY - 2022/8

Y1 - 2022/8

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85131512804&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85131512804&partnerID=8YFLogxK

U2 - 10.1007/s00236-022-00425-1

DO - 10.1007/s00236-022-00425-1

M3 - Article

AN - SCOPUS:85131512804

SN - 0001-5903

VL - 59

SP - 289

EP - 319

JO - Acta Informatica

JF - Acta Informatica

IS - 4

ER -

Depth-first search in directed planar graphs, revisited

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this