Polynomial-time recognition of clique-width ≤3 graphs

Abstract : Clique-width is a relatively new parameterization of graphs, philosophically similar to treewidth. Clique-width is more encompassing in the sense that a graph of bounded treewidth is also of bounded clique-width (but not the converse). For graphs of bounded clique-width, given the clique-width decomposition, every optimization, enumeration or evaluation problem that can be defined by a monadic second-order logic formula using quantifiers on vertices, but not on edges, can be solved in polynomial time. This is reminiscent of the situation for graphs of bounded treewidth, where the same statement holds even if quantifiers are also allowed on edges. Thus, graphs of bounded clique-width are a larger class than graphs of bounded treewidth, on which we can resolve fewer, but still many, optimization problems efficiently. One of the major open questions regarding clique-width is whether graphs of clique-width at most k, for fixed k, can be recognized in polynomial time. In this paper, we present the first polynomial-time algorithm (O(n²m)) to recognize graphs of clique-width at most 3.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2012, Fourth Workshop on Graph Classes, Optimization, and Width Parameters Bergen, Norway, October 2009: Bergen GROW 09, 160 (6), pp.834-865. 〈10.1016/j.dam.2011.03.020〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01274081
Contributeur : Michel Habib <>
Soumis le : lundi 15 février 2016 - 13:35:52
Dernière modification le : jeudi 15 novembre 2018 - 20:27:23

Lien texte intégral

Identifiants

Citation

Derek G. Corneil, Michel Habib, Jean-Marc Lanlignel, Bruce Reed, Udi Rotics. Polynomial-time recognition of clique-width ≤3 graphs. Discrete Applied Mathematics, Elsevier, 2012, Fourth Workshop on Graph Classes, Optimization, and Width Parameters Bergen, Norway, October 2009: Bergen GROW 09, 160 (6), pp.834-865. 〈10.1016/j.dam.2011.03.020〉. 〈hal-01274081〉

Partager

Métriques

Consultations de la notice

227