Recent developments on graphs of bounded clique-width

详细信息    查看全文

• 作者：Marcin Kamiń ; ski ; Vadim V. Lozin ; Martin Milanič
• 关键词：Clique-width ; Tree-width ; Rank-width ; Hereditary class
• 刊名：Discrete Applied Mathematics
• 出版年：2009
• 出版时间：28 June 2009
• 年：2009
• 卷：157
• 期：12
• 页码：2747-2761
• 全文大小：1302 K

文摘

Whether the clique-width of graphs in a certain class of graphs is bounded or not, is an important question from an algorithmic point of view, as many problems that are NP-hard in general admit polynomial-time solutions when restricted to graphs of bounded clique-width. Over the last few years, many classes of graphs have been shown to have bounded clique-width. For many others, this parameter has been proved to be unbounded. This paper provides a survey of recent results addressing this problem.