Clique-Width for 4-Vertex Forbidden Subgraphs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2006-07

AUTHORS

Andreas Brandstadt, Joost Engelfriet, Hoang-Oanh Le, Vadim V. Lozin

ABSTRACT

Clique-width of graphs is a major new concept with respect to efficiency of graph algorithms. 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 induced subgraphs of at most four vertices with respect to bounded or unbounded clique-width. More... »

PAGES

561-590

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00224-005-1199-1

DOI

http://dx.doi.org/10.1007/s00224-005-1199-1

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1014642335


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Rostock", 
          "id": "https://www.grid.ac/institutes/grid.10493.3f", 
          "name": [
            "Institut fur Informatik, Universitat Rostock, D-18051 Rostock, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Brandstadt", 
        "givenName": "Andreas", 
        "id": "sg:person.011555246476.21", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011555246476.21"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Leiden University", 
          "id": "https://www.grid.ac/institutes/grid.5132.5", 
          "name": [
            "LIACS, Leiden University, P.O. Box 9512, 2300 RA Leiden, The Netherlands"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Engelfriet", 
        "givenName": "Joost", 
        "id": "sg:person.014574236321.39", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014574236321.39"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Technical University of Berlin", 
          "id": "https://www.grid.ac/institutes/grid.6734.6", 
          "name": [
            "Fachbereich Informatik, Technische Fachhochschule Berlin, D-13353 Berlin, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Le", 
        "givenName": "Hoang-Oanh", 
        "id": "sg:person.014673067135.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014673067135.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Rutgers University", 
          "id": "https://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "RUTCOR, Rutgers University, 640 Bartholomew Rd., Piscataway, NJ 08854-8003, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lozin", 
        "givenName": "Vadim V.", 
        "id": "sg:person.015270564533.80", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015270564533.80"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2006-07", 
    "datePublishedReg": "2006-07-01", 
    "description": "Clique-width of graphs is a major new concept with respect to efficiency of graph algorithms. 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 induced subgraphs of at most four vertices with respect to bounded or unbounded clique-width.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00224-005-1199-1", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1052098", 
        "issn": [
          "1432-4350", 
          "1433-0490"
        ], 
        "name": "Theory of Computing Systems", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "39"
      }
    ], 
    "name": "Clique-Width for 4-Vertex Forbidden Subgraphs", 
    "pagination": "561-590", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "45c1da350b3c419a226a820cdccd7463ab8912713c959b91e5ce42dcc7b4d6f9"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00224-005-1199-1"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1014642335"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00224-005-1199-1", 
      "https://app.dimensions.ai/details/publication/pub.1014642335"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T18:14", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8675_00000487.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/s00224-005-1199-1"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00224-005-1199-1'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00224-005-1199-1'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00224-005-1199-1'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00224-005-1199-1'


 

This table displays all metadata directly associated to this object as RDF triples.

91 TRIPLES      20 PREDICATES      27 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00224-005-1199-1 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N31843abbca49405aa8cb41b66c262161
4 schema:datePublished 2006-07
5 schema:datePublishedReg 2006-07-01
6 schema:description Clique-width of graphs is a major new concept with respect to efficiency of graph algorithms. 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 induced subgraphs of at most four vertices with respect to bounded or unbounded clique-width.
7 schema:genre research_article
8 schema:inLanguage en
9 schema:isAccessibleForFree false
10 schema:isPartOf Na7e2d123ddcc4933a1ccf5e2eed651f7
11 Nf751388a2d054b4ea9ef6222a5396f7d
12 sg:journal.1052098
13 schema:name Clique-Width for 4-Vertex Forbidden Subgraphs
14 schema:pagination 561-590
15 schema:productId N7fc61ab063084bbaa046bc93e5d61ddd
16 Na668146982d84803986cc345f8099e36
17 Nf1de755220e64b45a26a0b2f4d174a9e
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014642335
19 https://doi.org/10.1007/s00224-005-1199-1
20 schema:sdDatePublished 2019-04-10T18:14
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher Nccbcae9eb5f54e29be93b096f8cf9d2f
23 schema:url http://link.springer.com/10.1007/s00224-005-1199-1
24 sgo:license sg:explorer/license/
25 sgo:sdDataset articles
26 rdf:type schema:ScholarlyArticle
27 N00ffaf7aa391484bbcf60950d7926bf3 rdf:first sg:person.015270564533.80
28 rdf:rest rdf:nil
29 N31843abbca49405aa8cb41b66c262161 rdf:first sg:person.011555246476.21
30 rdf:rest N39c7458e2cd14ae58614722383ee21f6
31 N39c7458e2cd14ae58614722383ee21f6 rdf:first sg:person.014574236321.39
32 rdf:rest N3d0e623245f940c9889e405d1fc0c135
33 N3d0e623245f940c9889e405d1fc0c135 rdf:first sg:person.014673067135.27
34 rdf:rest N00ffaf7aa391484bbcf60950d7926bf3
35 N7fc61ab063084bbaa046bc93e5d61ddd schema:name doi
36 schema:value 10.1007/s00224-005-1199-1
37 rdf:type schema:PropertyValue
38 Na668146982d84803986cc345f8099e36 schema:name dimensions_id
39 schema:value pub.1014642335
40 rdf:type schema:PropertyValue
41 Na7e2d123ddcc4933a1ccf5e2eed651f7 schema:issueNumber 4
42 rdf:type schema:PublicationIssue
43 Nccbcae9eb5f54e29be93b096f8cf9d2f schema:name Springer Nature - SN SciGraph project
44 rdf:type schema:Organization
45 Nf1de755220e64b45a26a0b2f4d174a9e schema:name readcube_id
46 schema:value 45c1da350b3c419a226a820cdccd7463ab8912713c959b91e5ce42dcc7b4d6f9
47 rdf:type schema:PropertyValue
48 Nf751388a2d054b4ea9ef6222a5396f7d schema:volumeNumber 39
49 rdf:type schema:PublicationVolume
50 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
51 schema:name Information and Computing Sciences
52 rdf:type schema:DefinedTerm
53 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
54 schema:name Computation Theory and Mathematics
55 rdf:type schema:DefinedTerm
56 sg:journal.1052098 schema:issn 1432-4350
57 1433-0490
58 schema:name Theory of Computing Systems
59 rdf:type schema:Periodical
60 sg:person.011555246476.21 schema:affiliation https://www.grid.ac/institutes/grid.10493.3f
61 schema:familyName Brandstadt
62 schema:givenName Andreas
63 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011555246476.21
64 rdf:type schema:Person
65 sg:person.014574236321.39 schema:affiliation https://www.grid.ac/institutes/grid.5132.5
66 schema:familyName Engelfriet
67 schema:givenName Joost
68 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014574236321.39
69 rdf:type schema:Person
70 sg:person.014673067135.27 schema:affiliation https://www.grid.ac/institutes/grid.6734.6
71 schema:familyName Le
72 schema:givenName Hoang-Oanh
73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014673067135.27
74 rdf:type schema:Person
75 sg:person.015270564533.80 schema:affiliation https://www.grid.ac/institutes/grid.430387.b
76 schema:familyName Lozin
77 schema:givenName Vadim V.
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015270564533.80
79 rdf:type schema:Person
80 https://www.grid.ac/institutes/grid.10493.3f schema:alternateName University of Rostock
81 schema:name Institut fur Informatik, Universitat Rostock, D-18051 Rostock, Germany
82 rdf:type schema:Organization
83 https://www.grid.ac/institutes/grid.430387.b schema:alternateName Rutgers University
84 schema:name RUTCOR, Rutgers University, 640 Bartholomew Rd., Piscataway, NJ 08854-8003, USA
85 rdf:type schema:Organization
86 https://www.grid.ac/institutes/grid.5132.5 schema:alternateName Leiden University
87 schema:name LIACS, Leiden University, P.O. Box 9512, 2300 RA Leiden, The Netherlands
88 rdf:type schema:Organization
89 https://www.grid.ac/institutes/grid.6734.6 schema:alternateName Technical University of Berlin
90 schema:name Fachbereich Informatik, Technische Fachhochschule Berlin, D-13353 Berlin, Germany
91 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...