A random NC algorithm for depth first search

From MaRDI portal





We present a fast parallel algorithm for constructing a depth first search tree for an undirected graph. The algorithms is an RNC algorithm, meaning that it is a probabilistic algorithm that runs in polylog time using a polynomial number of processors on a P-RAM. The run time of the algorithm is \(O(T_{MM}(n)\log^ 3 n)\), and the number of processors used is \(P_{MM}(n)\) where \(T_{MM}n)\) and \(P_{MM}(n)\) are the time and number of processors needed to find a minimum weight perfect matching on an n vertex graph with maximum edge weight n.




Cited in
(24)








This page was built for publication: A random NC algorithm for depth first search

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1104756)