Bibliographic Details
| Title: |
Query efficient implementation of graphs of bounded clique-width |
| Authors: |
Courcelle, B. courcell@labri.fr, Vanicat, R.1 |
| Source: |
Discrete Applied Mathematics. Sep2003, Vol. 131 Issue 1, p129. 22p. |
| Subjects: |
Graphic methods, Algorithms, Mathematical optimization, Mathematical functions, Mathematics |
| Abstract: |
If P(x1,…,xk) is a graph property expressible in monadic second-order logic, where x1,…,xk denote vertices, if G is a graph with n vertices and of clique-width at most p where p is fixed, then we can associate with each vertex u of G a piece of information I(u) of size O(log(n)) such that, for all vertices x1,…,xk of G, one can decide whether P(x1,…,xk) holds in time O(log(n)) by using only I(x1),…,I(xk). The preprocessing can be done in time O(n log(n)).One can do the same for any fixed monadic second-order optimization function (like distance) by using information of size O(log2(n)) for each vertex and computation time O(log2(n)). In this case preprocessing time is O(–log2(n)).Clique-width is a complexity measure on graphs similar to tree-width, but more powerful since every set of graphs of bounded tree-width has bounded clique-width, but not conversely.Similar results apply to graphs of tree-width at most w and to properties and functions expressed in the version of monadic second-order logic allowing quantifications on sets of edges. [Copyright &y& Elsevier] |
|
Copyright of Discrete Applied Mathematics is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Engineering Source |
