Computing the pathwidth of directed graphs with small vertex cover

• Yasuaki Kobayashi

  Gakushuin University

抄録

We give an algorithm that computes the pathwidth of a given directed graph D in 3τ(D)nO(1) time where n is the number of vertices of D and τ(D) is the number of vertices of a minimum vertex cover of the underlying graph of D. This result extends that of [Chapelle et al., 2013] for undirected graphs to directed graphs. Moreover, our algorithm is based on a standard dynamic programming with a simple tree-pruning trick, which is extremely simple and easy to implement.
We give an algorithm that computes the pathwidth of a given directed graph D in 3γ(D)nO(1) time where n is the number of vertices of D and γ(D) is the number of vertices of a minimum vertex cover of the underlying graph of D. This result extends that of [Chapelle et al., 2013] for undirected graphs to directed graphs. Moreover, our algorithm is based on a standard dynamic programming with a simple tree-pruning trick, which is extremely simple and easy to implement.

収録刊行物

• 情報処理学会研究報告. AL, アルゴリズム研究会報告

  情報処理学会研究報告. AL, アルゴリズム研究会報告 2014 (16), 1-2, 2014-06-06

  一般社団法人情報処理学会

詳細情報

• CRID: 1573950402607123840
• NII論文ID: 110009785576
• NII書誌ID: AN1009593X
• ISSN: 09196072
• 本文言語コード: en
• データソース種別:
  • CiNii Articles