Abstract | ||
---|---|---|
This article establishes that the split decomposition of graphs introduced by Cunnigham, is definable in Monadic Second-Order Logic. This result is actually an instance of a more general result covering canonical graph decompositions like the modular decomposition and the Tutte decomposition of 2-connected graphs into 3-connected components. As an application, we prove that the set of graphs having the same cycle matroid as a given 2-connected graph can be defined from this graph by Monadic Second-Order formulas. |
Year | DOI | Venue |
---|---|---|
2005 | 10.2168/LMCS-2(2:2)2006 | LOGICAL METHODS IN COMPUTER SCIENCE |
Keywords | DocType | Volume |
Monadic second-order logic,split decomposition,modular decomposition,clique-width | Journal | 2 |
Issue | ISSN | Citations |
2 | 1860-5974 | 7 |
PageRank | References | Authors |
0.45 | 21 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Bruno Courcelle | 1 | 3418 | 388.00 |
Erich Grädel | 2 | 1211 | 114.35 |