A linear-time parameterized algorithm for computing the width of a DAG

Manuel Cáceres, Massimo Cairo, Brendan Mumey +2

The width $k$ of a directed acyclic graph (DAG) $G=(V,E)$ equals the largest number of pairwise non-reachable vertices. Computing the width dates back to Dilworth's and Fulkerso…