Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420467 | Discrete Applied Mathematics | 2009 | 15 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Marcin Kamiński, Vadim V. Lozin, Martin Milanič,