Domino treewidth View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1995

AUTHORS

Hans L. Bodlaender , Joost Engelfriet

ABSTRACT

We consider a special variant of tree-decompositions, called domino tree-decompositions, and the related notion of domino treewidth. In a domino tree-decomposition, each vertex of the graph belongs to at most two nodes of the tree. We prove that for every k, d, there exists a constant C k,d such that a graph with treewidth at most k and maximum degree at most d has domino treewidth at most C k,d The domino treewidth of a tree can be computed in O(n 2 log n) time. There exist polynomial time algorithms that — for fixed k — decide whether a given graph G has domino treewidth at most k. If k is not fixed, this problem is NP-complete. The domino treewidth problem is hard for the complexity classes W[t] for all t ξ N, and hence the problem for fixed k is unlikely to be solvable in O(n c ), where c is a constant, not depending on k. More... »

PAGES

1-13

Book

TITLE

Graph-Theoretic Concepts in Computer Science

ISBN

978-3-540-59071-2
978-3-540-49183-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-59071-4_33

DOI

http://dx.doi.org/10.1007/3-540-59071-4_33

DIMENSIONS

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


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": "Utrecht University", 
          "id": "https://www.grid.ac/institutes/grid.5477.1", 
          "name": [
            "Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508\u00a0TB Utrecht, The Netherlands"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bodlaender", 
        "givenName": "Hans L.", 
        "id": "sg:person.07607532415.25", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07607532415.25"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Leiden University", 
          "id": "https://www.grid.ac/institutes/grid.5132.5", 
          "name": [
            "Department of Computer Science, Leiden University, P.O. Box 9512, 2300\u00a0RA 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"
      }
    ], 
    "datePublished": "1995", 
    "datePublishedReg": "1995-01-01", 
    "description": "We consider a special variant of tree-decompositions, called domino tree-decompositions, and the related notion of domino treewidth. In a domino tree-decomposition, each vertex of the graph belongs to at most two nodes of the tree. We prove that for every k, d, there exists a constant C k,d such that a graph with treewidth at most k and maximum degree at most d has domino treewidth at most C k,d The domino treewidth of a tree can be computed in O(n 2 log n) time. There exist polynomial time algorithms that \u2014 for fixed k \u2014 decide whether a given graph G has domino treewidth at most k. If k is not fixed, this problem is NP-complete. The domino treewidth problem is hard for the complexity classes W[t] for all t \u03be N, and hence the problem for fixed k is unlikely to be solvable in O(n c ), where c is a constant, not depending on k.", 
    "editor": [
      {
        "familyName": "Mayr", 
        "givenName": "Ernst W.", 
        "type": "Person"
      }, 
      {
        "familyName": "Schmidt", 
        "givenName": "Gunther", 
        "type": "Person"
      }, 
      {
        "familyName": "Tinhofer", 
        "givenName": "Gottfried", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-59071-4_33", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-59071-2", 
        "978-3-540-49183-5"
      ], 
      "name": "Graph-Theoretic Concepts in Computer Science", 
      "type": "Book"
    }, 
    "name": "Domino treewidth", 
    "pagination": "1-13", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-59071-4_33"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "265005c6dc0624c4a8892b0f0fe0bf938b5f8d486dbb2523198dc83abec54cbb"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1008041858"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-59071-4_33", 
      "https://app.dimensions.ai/details/publication/pub.1008041858"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T12:15", 
    "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_8663_00000013.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-59071-4_33"
  }
]
 

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/3-540-59071-4_33'

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/3-540-59071-4_33'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-59071-4_33'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-59071-4_33'


 

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

85 TRIPLES      22 PREDICATES      27 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-59071-4_33 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N4aaa0bfe0cb24ec4ab297813ad316862
4 schema:datePublished 1995
5 schema:datePublishedReg 1995-01-01
6 schema:description We consider a special variant of tree-decompositions, called domino tree-decompositions, and the related notion of domino treewidth. In a domino tree-decomposition, each vertex of the graph belongs to at most two nodes of the tree. We prove that for every k, d, there exists a constant C k,d such that a graph with treewidth at most k and maximum degree at most d has domino treewidth at most C k,d The domino treewidth of a tree can be computed in O(n 2 log n) time. There exist polynomial time algorithms that — for fixed k — decide whether a given graph G has domino treewidth at most k. If k is not fixed, this problem is NP-complete. The domino treewidth problem is hard for the complexity classes W[t] for all t ξ N, and hence the problem for fixed k is unlikely to be solvable in O(n c ), where c is a constant, not depending on k.
7 schema:editor N66ad5308bb674bf7b286787406bddb3a
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N263dd2f098b64e23b7cbac47db294d5f
12 schema:name Domino treewidth
13 schema:pagination 1-13
14 schema:productId N1b26bb2124544fc599f36ff68f65ed61
15 N4f45b88e8bc6432f9fe52df43aab2dcf
16 Neeaa086b7ad1472388de9e4665d95f10
17 schema:publisher Nfb0c49a5f26b47478b7c23ae5333b471
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008041858
19 https://doi.org/10.1007/3-540-59071-4_33
20 schema:sdDatePublished 2019-04-15T12:15
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher Na027faaec769405eb1bc4d0e5a34cbfc
23 schema:url http://link.springer.com/10.1007/3-540-59071-4_33
24 sgo:license sg:explorer/license/
25 sgo:sdDataset chapters
26 rdf:type schema:Chapter
27 N1b26bb2124544fc599f36ff68f65ed61 schema:name dimensions_id
28 schema:value pub.1008041858
29 rdf:type schema:PropertyValue
30 N24a26fd4b0f54789a9118e91c4d4b61b rdf:first sg:person.014574236321.39
31 rdf:rest rdf:nil
32 N263dd2f098b64e23b7cbac47db294d5f schema:isbn 978-3-540-49183-5
33 978-3-540-59071-2
34 schema:name Graph-Theoretic Concepts in Computer Science
35 rdf:type schema:Book
36 N34e92be507c745378b11619a54f1f0e7 schema:familyName Tinhofer
37 schema:givenName Gottfried
38 rdf:type schema:Person
39 N4aaa0bfe0cb24ec4ab297813ad316862 rdf:first sg:person.07607532415.25
40 rdf:rest N24a26fd4b0f54789a9118e91c4d4b61b
41 N4f45b88e8bc6432f9fe52df43aab2dcf schema:name doi
42 schema:value 10.1007/3-540-59071-4_33
43 rdf:type schema:PropertyValue
44 N5809630ad5004c2b88619a8bba0ed393 rdf:first Nfb90c6c73fab40f68c11c145d1159ec5
45 rdf:rest Na6412c5fad6f4c9fb5a971552987ad99
46 N6592be7711a24d1aaa0cb88ba602840b schema:familyName Mayr
47 schema:givenName Ernst W.
48 rdf:type schema:Person
49 N66ad5308bb674bf7b286787406bddb3a rdf:first N6592be7711a24d1aaa0cb88ba602840b
50 rdf:rest N5809630ad5004c2b88619a8bba0ed393
51 Na027faaec769405eb1bc4d0e5a34cbfc schema:name Springer Nature - SN SciGraph project
52 rdf:type schema:Organization
53 Na6412c5fad6f4c9fb5a971552987ad99 rdf:first N34e92be507c745378b11619a54f1f0e7
54 rdf:rest rdf:nil
55 Neeaa086b7ad1472388de9e4665d95f10 schema:name readcube_id
56 schema:value 265005c6dc0624c4a8892b0f0fe0bf938b5f8d486dbb2523198dc83abec54cbb
57 rdf:type schema:PropertyValue
58 Nfb0c49a5f26b47478b7c23ae5333b471 schema:location Berlin, Heidelberg
59 schema:name Springer Berlin Heidelberg
60 rdf:type schema:Organisation
61 Nfb90c6c73fab40f68c11c145d1159ec5 schema:familyName Schmidt
62 schema:givenName Gunther
63 rdf:type schema:Person
64 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
65 schema:name Information and Computing Sciences
66 rdf:type schema:DefinedTerm
67 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
68 schema:name Computation Theory and Mathematics
69 rdf:type schema:DefinedTerm
70 sg:person.014574236321.39 schema:affiliation https://www.grid.ac/institutes/grid.5132.5
71 schema:familyName Engelfriet
72 schema:givenName Joost
73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014574236321.39
74 rdf:type schema:Person
75 sg:person.07607532415.25 schema:affiliation https://www.grid.ac/institutes/grid.5477.1
76 schema:familyName Bodlaender
77 schema:givenName Hans L.
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07607532415.25
79 rdf:type schema:Person
80 https://www.grid.ac/institutes/grid.5132.5 schema:alternateName Leiden University
81 schema:name Department of Computer Science, Leiden University, P.O. Box 9512, 2300 RA Leiden, the Netherlands
82 rdf:type schema:Organization
83 https://www.grid.ac/institutes/grid.5477.1 schema:alternateName Utrecht University
84 schema:name Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508 TB Utrecht, The Netherlands
85 rdf:type schema:Organization
 




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


...