  We present practical linear and almost linear-time algorithms to compute a
chain decomposition of a directed acyclic graph (DAG), $G=(V,E)$. The number of
vertex-disjoint chains computed is very close to the minimum. The time
complexity of our algorithm is $O(|E|+c*l)$, where $c$ is the number of path
concatenations and $l$ is the length of a longest path of the graph. We give a
comprehensive explanation on factors $c$ and $l$ in the following sections. Our
techniques have important applications in many areas, including the design of
faster practical transitive closure algorithms. We observe that $|E_{red}|\leq
width*|V|$ ($E_{red}$: non-transitive edges) and show how to find a
substantially large subset of $E_{tr}$ (transitive edges) using a chain
decomposition in linear time, without calculating the transitive closure. Our
extensive experimental results show the interplay between the width, $E_{red}$,
$E_{tr}$ in various models of graphs. We show how to compute a reachability
indexing scheme in $O(k_c*|E_{red}|)$ time, where $k_c$ is the number of chains
and $|E_{red}|$ is the number of non-transitive edges. This scheme can answer
reachabilitiy queries in constant time. The space complexity of the scheme is
$O(k_c*|V|)$. The experimental results reveal that our methods are even better
in practice than the theoretical bounds imply, indicating how fast chain
decomposition algorithms can be applied to the transitive closure problem.
