Depth-First Search Using $$O(n)$$ Bits
type: Item
instance of: scholarly article
title: Depth-First Search Using $$O(n)$$ Bits
zbMATH Open document ID: 1430.68172
DOI: 10.1007/978-3-319-13075-0_44
author: Taisuke Izumi
author: Masashi Kiyomi
author: Matsuo Konagaya
author: Hirotaka Ono
author: Yota Otachi
author: P. Schweitzer
author: Jun Tarui
author: Ryuhei Uehara
author: Tetsuo Asano
published in: Algorithms and Computation
publication date: 2015-09-11T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 6480942
MaRDI profile type: Publication
full work available at URL: 978-3-319-13075-0 44
OpenAlex ID: W2284006119
cites work: A random NC algorithm for depth first search
cites work: Parallelism and the maximal path problem
cites work: Priority Queues and Sorting for Read-Only Data
cites work: Time-Space Tradeoffs for All-Nearest-Larger-Neighbors Problems
cites work: $\widetilde{O}(\sqrt{n})$ -Space and Polynomial-Time Algorithm for Planar Directed Graph Reachability
cites work: A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
cites work: Embedding and canonizing graphs of bounded genus in logspace
cites work: Q4298260
cites work: Depth-first search is inherently sequential
cites work: Undirected connectivity in log-space
cites work: Depth-First Search and Linear Graph Algorithms
cites work: Fast Parallel Algorithms for All-Sources Lexicographic Search and Path-Algebra Problems
cites work: Polynomially improved efficiency for fast parallel single-source lexicographic depth-first search, breadth-first search, and topological-first search
Recommended article: Q4356435
Recommended article: Q3753485
Recommended article: Q3719851
Recommended article: Depth-First Search with P Systems
Recommended article: The number of depth-first searches of an ordered set
Recommended article: A random NC algorithm for depth first search
Recommended article: Planar Depth-First Search in $O(\log n)$ Parallel Time
Recommended article: Depth-First Mini-Bucket Elimination
Recommended article: Q4028920
description: scientific article