Parallel Complexity of Depth-First-Search and Maximal path in restricted graph classes

Archit Chauhan, Samir Datta, M. Praveen

Constructing a Depth First Search (DFS) tree is a fundamental graph problem, whose parallel complexity is still not settled. Reif showed parallel intractability of lex-first DFS. I…