<p>Depth-First-Search (DFS) has a quasilinear (i.e.,<span class="math-container">$\widetilde{O}(m+n)$</span>) time algorithm in random access model (RAM). I am curious about whether DFS still admits a <span class="math-container">$\widetilde{O}(m+n)$</span> time algorithm in multitape Turing machine model.</p>

CC BY-SA 4.0
2019-07-23T15:18:52.710Z
For the "linear" part, I guess no, since you need an extra-factor $O(\log n)$ to read the node IDs.
Lamine
CC BY-SA 4.0
2019-07-24T14:44:24.800Z
I don't care about the log factor. Quasilinear (i.e., $\widetilde{O}(m+n)$) time algorithm will be OK.
Qian
CC BY-SA 4.0
2019-07-24T15:04:38.903Z
You don't care about in your new edited question. The previous one,  which I commented, asked for "a linear or quasilinear" algorithm.
Lamine
<graph-algorithms><circuit-complexity><time-complexity><turing-machines>
Does Depth-First-Search admit a quasilinear time algorithm in mutitape Turing Machine model?
Qian
# Does Depth-First-Search admit a quasilinear time algorithm in mutitape Turing Machine model?

(Asked by: username_0 on 2019-07-19)

Depth-First-Search (DFS) has a quasilinear (i.e.,$\widetilde{O}(m+n)$) time algorithm in random access model (RAM). I am curious about whether DFS still admits a $\widetilde{O}(m+n)$ time algorithm in multitape Turing machine model.

**Tags:** graph-algorithms, circuit-complexity, time-complexity, turing-machines

> **Comments:**
> **username_1**: For the "linear" part, I guess no, since you need an extra-factor $O(\log n)$ to read the node IDs.  
> **username_0**: I don't care about the log factor. Quasilinear (i.e., $\widetilde{O}(m+n)$) time algorithm will be OK.  
> **username_1**: You don't care about in your new edited question. The previous one,  which I commented, asked for "a linear or quasilinear" algorithm.  

---

## 0 answers

