View in EDS

Query efficient implementation of graphs of bounded clique-width

Saved in:
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
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 10695098
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Query efficient implementation of graphs of bounded clique-width
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Courcelle%2C+B%2E%22">Courcelle, B.</searchLink><i> courcell@labri.fr</i><br /><searchLink fieldCode="AR" term="%22Vanicat%2C+R%2E%22">Vanicat, R.</searchLink><relatesTo>1</relatesTo>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Discrete+Applied+Mathematics%22">Discrete Applied Mathematics</searchLink>. Sep2003, Vol. 131 Issue 1, p129. 22p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Graphic+methods%22">Graphic methods</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+optimization%22">Mathematical optimization</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+functions%22">Mathematical functions</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematics%22">Mathematics</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: If <f>P(x1,…,xk)</f> is a graph property expressible in monadic second-order logic, where <f>x1,…,xk</f> denote vertices, if <f>G</f> is a graph with <f>n</f> vertices and of clique-width at most <f>p</f> where <f>p</f> is fixed, then we can associate with each vertex <f>u</f> of <f>G</f> a piece of information <f>I(u)</f> of size <f>O(log(n))</f> such that, for all vertices <f>x1,…,xk</f> of <f>G</f>, one can decide whether <f>P(x1,…,xk)</f> holds in time <f>O(log(n))</f> by using only <f>I(x1),…,I(xk)</f>. The preprocessing can be done in time <f>O(n log(n))</f>.One can do the same for any fixed monadic second-order optimization function (like distance) by using information of size <f>O(log2(n))</f> for each vertex and computation time <f>O(log2(n))</f>. In this case preprocessing time is <f>O(–log2(n))</f>.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 <f>w</f> and to properties and functions expressed in the version of monadic second-order logic allowing quantifications on sets of edges. [Copyright &y& Elsevier]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>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.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=10695098
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/S0166-218X(02)00421-3
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 22
        StartPage: 129
    Subjects:
      – SubjectFull: Graphic methods
        Type: general
      – SubjectFull: Algorithms
        Type: general
      – SubjectFull: Mathematical optimization
        Type: general
      – SubjectFull: Mathematical functions
        Type: general
      – SubjectFull: Mathematics
        Type: general
    Titles:
      – TitleFull: Query efficient implementation of graphs of bounded clique-width
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Courcelle, B.
      – PersonEntity:
          Name:
            NameFull: Vanicat, R.
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 06
              M: 09
              Text: Sep2003
              Type: published
              Y: 2003
          Identifiers:
            – Type: issn-print
              Value: 0166218X
          Numbering:
            – Type: volume
              Value: 131
            – Type: issue
              Value: 1
          Titles:
            – TitleFull: Discrete Applied Mathematics
              Type: main
ResultId 1