5
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ For the "linear" part, I guess no, since you need an extra-factor $O(\log n)$ to read the node IDs. $\endgroup$
    – Lamine
    Jul 23, 2019 at 15:18
  • $\begingroup$ I don't care about the log factor. Quasilinear (i.e., $\widetilde{O}(m+n)$) time algorithm will be OK. $\endgroup$
    – Qian
    Jul 24, 2019 at 14:44
  • 1
    $\begingroup$ You don't care about in your new edited question. The previous one, which I commented, asked for "a linear or quasilinear" algorithm. $\endgroup$
    – Lamine
    Jul 24, 2019 at 15:04

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy