Computing the pathwidth of directed graphs with small vertex cover

作     者：Kobayashi, Yasuaki 

作者机构：Gakushuin Univ Ctr Comp Toshima Ku Tokyo 1718588 Japan 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：2015年第115卷第2期

页      面：310-312页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Grants-in-Aid for Scientific Research Funding Source: KAKEN 

主　　题：Graph algorithms Fixed parameter tractable Pathwidth Vertex cover Vertex separation 

摘      要：We give an algorithm that computes the pathwidth of a given directed graph D in 3(tau(D))n(0(1)) time where n is the number of vertices of D and tau(D) is the number of vertices of a minimum vertex cover of the underlying undirected graph of D. This result extends that of [5] 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. An additional advantage of our algorithm is that a minimum vertex cover appears in the analysis but not in the algorithm itself, in contrast to the algorithm of [5] which needs to compute a minimum vertex cover. (C) 2014 Elsevier B.V. All rights reserved.