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

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

研究成果: Article

6 引用 (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.

元の言語English
ページ(範囲)138-157
ページ数20
ジャーナルAlgorithmica
75
発行部数1
DOI
出版物ステータスPublished - 1 5 2016

フィンガープリント Computing Directed Pathwidth in O(1. 89 <sup>n</sup>) Time' の研究トピックを掘り下げます。これらはともに一意のフィンガープリントを構成します。

  • これを引用

    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