Editing Depth-first search (section)

==Complexity==
The [[Analysis of algorithms|computational complexity]] of DFS was investigated by [[John Reif]]. More precisely, given a graph <math>G</math>, let <math>O=(v_1,\dots,v_n)</math> be the ordering computed by the standard recursive DFS algorithm. This ordering is called the lexicographic depth-first search ordering. John Reif considered the complexity of computing the lexicographic depth-first search ordering, given a graph and a source. A [[decision problem|decision version]] of the problem (testing whether some vertex {{mvar|u}} occurs before some vertex {{mvar|v}} in this order) is [[P-complete|'''P'''-complete]],<ref>{{Cite journal| doi = 10.1016/0020-0190(85)90024-9| title = Depth-first search is inherently sequential| journal = Information Processing Letters| volume = 20| issue = 5| year = 1985| last1 = Reif | first1 = John H. | pages = 229–234}}</ref> meaning that it is "a nightmare for [[parallel algorithm|parallel processing]]".<ref name="mehlhorn">{{cite book |last1=Mehlhorn |first1=Kurt |author1-link=Kurt Mehlhorn|first2=Peter |last2=Sanders|author2-link=Peter Sanders (computer scientist) |title=Algorithms and Data Structures: The Basic Toolbox |publisher=Springer |year=2008 |url=http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/GraphTraversal.pdf |archive-url=https://web.archive.org/web/20150908084757/http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/GraphTraversal.pdf |archive-date=2015-09-08 |url-status=live}}</ref>{{rp|189}}

A depth-first search ordering (not necessarily the lexicographic one), can be computed by a randomized parallel algorithm in the complexity class [[NC (complexity)|RNC]].<ref>{{citation
 | last1 = Aggarwal | first1 = A.
 | last2 = Anderson | first2 = R. J.
 | doi = 10.1007/BF02122548
 | issue = 1
 | journal = [[Combinatorica]]
 | mr = 951989
 | pages = 1–12
 | title = A random ''NC'' algorithm for depth first search
 | volume = 8
 | year = 1988| s2cid = 29440871
 }}.</ref> As of 1997, it remained unknown whether a depth-first traversal could be constructed by a deterministic parallel algorithm, in the complexity class [[NC (complexity)|NC]].<ref>{{citation
 | last1 = Karger | first1 = David R. | author1-link = David Karger
 | last2 = Motwani | first2 = Rajeev | author2-link = Rajeev Motwani
 | doi = 10.1137/S0097539794273083
 | issue = 1
 | journal = [[SIAM Journal on Computing]]
 | mr = 1431256
 | pages = 255–272
 | title = An ''NC'' algorithm for minimum cuts
 | volume = 26
 | year = 1997| citeseerx = 10.1.1.33.1701}}.</ref>