Depth-first search in directed planar graphs, revisited

Autor:	Allender, Eric, Chauhan, Archit, Datta, Samir
Rok vydání:	2022
Předmět:	Computer Networks and Communications Theory of computation → Parallel algorithms Parallel Algorithms Space-Bounded Complexity Classes Depth-First Search Planar Digraphs Theory of computation → Complexity classes Software Information Systems
Zdroj:	Acta Informatica. 59:289-319
ISSN:	1432-0525 0001-5903
DOI:	10.1007/s00236-022-00425-1
Popis:	We present an algorithm for constructing a depth-first search tree in planar digraphs; the algorithm can be implemented in the complexity class AC^1(UL∩co-UL), which is contained in AC². Prior to this (for more than a quarter-century), the fastest uniform deterministic parallel algorithm for this problem was O(log^{10}n) (corresponding to the complexity class AC^{10} ⊆ NC^{11}). We also consider the problem of computing depth-first search trees in other classes of graphs, and obtain additional new upper bounds. LIPIcs, Vol. 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), pages 7:1-7:22
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::71cc1a4ef2c11b520763a9bfde80fc9a https://doi.org/10.1007/s00236-022-00425-1 Zobrazit plný text záznamu Plný text ve formátu PDF Plný text ve formátu HTML
Nepřihlášeným uživatelům se plný text nezobrazuje	K zobrazení výsledku je třeba se přihlásit.