TREEWIDTH AND PATHWIDTH OF PERMUTATION GRAPHS

作     者：BODLAENDER, HL KLOKS, T KRATSCH, D 

作者机构：EINDHOVEN UNIV TECHNOLDEPT MATH & COMP SCI5600 MB EINDHOVENNETHERLANDS UNIV JENAFAK MATH & INFORMATD-07740 JENAGERMANY 

出 版 物：《SIAM JOURNAL ON DISCRETE MATHEMATICS》 (工业与应用数学会离散数学杂志)

年 卷 期：1995年第8卷第4期

页      面：606-616页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：PERMUTATION GRAPHS GRAPH ALGORITHMS TREEWIDTH 

摘      要：In this paper, we show that the treewidth and pathwidth of a permutation graph can be computed in polynomial time. In fact we show that, for permutation graphs, the treewidth and pathwidth are equal. These results make permutation graphs one of the few nontrivial graph classes for which, at the moment, treewidth is known to be computable in polynomial time. Our algorithm, which decides whether the treewidth (pathwidth) is at most some given integer Ic, can be implemented to run in O(nk) time when the matching diagram is given. We show that this algorithm can easily be adapted to compute the pathwidth of a permutation graph in O(nk) time, where k is the pathwidth.