The clique-width of graphs is a major new concept with respect to the efficiency of graph algorithms; it is known that every problem expressible in a certain kind of Monadic Second Order Logic called LinEMSOL(τ1,L) by Courcelle et al. is linear-time solvable on any graph class with bounded clique-width for which a k-expression for the input graph can be constructed in linear time. The notion of clique-width extends the one of treewidth since bounded treewidth implies bounded clique-width. We give a complete classification of all graph classes defined by forbidden one-vertex extensions of the P4 (i.e., the path with four vertices a,b,c,d and three edges ab,bc,cd) with respect to bounded clique-width. Our results extend and improve recent structural and complexity results in a systematic way.
New graph classes of bounded clique-width
MOSCA, Raffaele
2005-01-01
Abstract
The clique-width of graphs is a major new concept with respect to the efficiency of graph algorithms; it is known that every problem expressible in a certain kind of Monadic Second Order Logic called LinEMSOL(τ1,L) by Courcelle et al. is linear-time solvable on any graph class with bounded clique-width for which a k-expression for the input graph can be constructed in linear time. The notion of clique-width extends the one of treewidth since bounded treewidth implies bounded clique-width. We give a complete classification of all graph classes defined by forbidden one-vertex extensions of the P4 (i.e., the path with four vertices a,b,c,d and three edges ab,bc,cd) with respect to bounded clique-width. Our results extend and improve recent structural and complexity results in a systematic way.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
