We give an algorithm for computing the directed pathwidth of a digraph with n vertices in O(1. 89 n) time. This is the first algorithm with running time better than the straightforward O∗(2 n). As a special case, it computes the pathwidth of an undirected graph in the same amount of time, improving on the algorithm due to Suchan and Villanger which runs in O(1. 9657 n) time.
- Exact exponential algorithm
- Graph algorithm