An EfRcient EREW Algorithm for Minimum Path Csver and Hamiltonicity on Covaphs
Rong Lin · 1993
We show that the notoriously dificult problem of finding the minimum number of paths that cover the vertices of a graph can be solved efficiently for cographs. Our result implies that for this class of graphs finding a hamiltonian path and a hamiltonian cycle can be solved eficiently in parallel. Specifically, with an n-veriez wgraph G represented by its parse tree as input, our algorithm determines the number of paths in a minimum path cover in Oflogn) time using & processors in the EREW-PRAM; we also exhibit all the paths in a minimum path cover of G in O(log2n) tame using & processors in the EREWPRAM. Our result significantly improves on the state of the art.