Algorithms For Longest Chains In Pseudo- Transitive Graphs

Farhad Shahrokhi

A directed acyclic graph G = (V, E) is pseudo-transitive with respect to a given subset of edges E1, if for any edge ab in E1 and any edge bc in E, we have ac in E. We give algorit…