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 treepruning 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 treepruning trick, which is extremely simple and easy to implement.
Journal

 IPSJ SIG Notes

IPSJ SIG Notes 2014AL148(16), 12, 20140606
Information Processing Society of Japan (IPSJ)