Computing Directed Pathwidth in O(1. 89 n) Time

Kenta Kitsunai, Yasuaki Kobayashi, Keita Komuro, Hisao Tamaki, Toshihiro Tano

Research output: Contribution to journalArticle

6 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)138-157
Number of pages20
Issue number1
Publication statusPublished - 1 May 2016


  • Exact exponential algorithm
  • Graph algorithm
  • Pathwidth

Fingerprint Dive into the research topics of 'Computing Directed Pathwidth in O(1. 89 <sup>n</sup>) Time'. Together they form a unique fingerprint.

  • Cite this

    Kitsunai, K., Kobayashi, Y., Komuro, K., Tamaki, H., & Tano, T. (2016). Computing Directed Pathwidth in O(1. 89 n) Time. Algorithmica, 75(1), 138-157.