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)

Abstract

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
JournalAlgorithmica
Volume75
Issue number1
DOIs
Publication statusPublished - 1 May 2016

Keywords

  • 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. https://doi.org/10.1007/s00453-015-0015-9