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.

$\endgroup$
  • $\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 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 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 at 15:04

Your Answer

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

Browse other questions tagged or ask your own question.