Computing the pathwidth of directed graphs with small vertex cover Computing the pathwidth of directed graphs with small vertex cover

Search this Article

Author(s)

Abstract

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.

Journal

  • IPSJ SIG Notes

    IPSJ SIG Notes 2014-AL-148(16), 1-2, 2014-06-06

    Information Processing Society of Japan (IPSJ)

Codes

  • NII Article ID (NAID)
    110009785576
  • NII NACSIS-CAT ID (NCID)
    AN1009593X
  • Text Lang
    ENG
  • ISSN
    09196072
  • Data Source
    NII-ELS 
Page Top