Linear Algorithms for Chordal Graphs of Bounded Directed Vertex Leafage

详细信息    查看全文

• 作者：Michel Habib ; Juraj Stacho
• 关键词：path graph ; chordal graph ; colouring ; clique ; linear algorithms
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2009
• 出版时间：15 March 2009
• 年：2009
• 卷：32
• 期：Complete
• 页码：99-108
• 全文大小：239 K

文摘

The directed vertex leafage of a chordal graph G is the smallest integer k such that G is the intersection graph of subtrees of a rooted directed tree where each subtree has at most k leaves. In this note, we show how to find in time O(kn) an optimal colouring, a maximum independent set, a maximum clique, and an optimal clique cover of an n-vertex chordal graph G with directed vertex leafage k if a representation of G is given. In particular, this implies that for any path graph G, the four problems can be solved in time O(n) given a path representation of G.