Treewidth of cocomparability graphs and a new order-theoretic parameter View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1994-03

AUTHORS

Michel Habib, Rolf H. Möhring

ABSTRACT

We show that the pathwidth of a cocomparability graphG equals its treewidth. The proof is based on a new notion, calledinterval width, for a partial orderP, which is the smallest width of an interval order contained inP, and which is shown to be equal to the treewidth of its cocomparability graph. We observe also that determining any of these parameters isNP-hard and we establish some connections between classical dimension notions of partial orders and interval width. In fact we develop approximation algorithms for interval width ofP whose performance ratios depend on the dimension and interval dimension ofP, respectively. More... »

PAGES

47-60

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf01462229

DOI

http://dx.doi.org/10.1007/bf01462229

DIMENSIONS

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


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": "Montpellier Laboratory of Informatics, Robotics and Microelectronics", 
          "id": "https://www.grid.ac/institutes/grid.464638.b", 
          "name": [
            "LIRMM, 161 rue Ada, 34392, Montpellier, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Habib", 
        "givenName": "Michel", 
        "id": "sg:person.012600773121.44", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012600773121.44"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Technical University of Berlin", 
          "id": "https://www.grid.ac/institutes/grid.6734.6", 
          "name": [
            "Fachbereich Mathematik, Technische Universit\u00e4t Berlin, 1000, Berlin 12, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "M\u00f6hring", 
        "givenName": "Rolf H.", 
        "id": "sg:person.011470250675.54", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011470250675.54"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf01934985", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001971810", 
          "https://doi.org/10.1007/bf01934985"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01934985", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001971810", 
          "https://doi.org/10.1007/bf01934985"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-94-009-2639-4_4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012529275", 
          "https://doi.org/10.1007/978-94-009-2639-4_4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-7091-9076-0_2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012939792", 
          "https://doi.org/10.1007/978-3-7091-9076-0_2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0304-0208(08)73832-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036569865"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-46908-4_70", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037858395", 
          "https://doi.org/10.1007/978-3-642-46908-4_70"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0012-365x(91)90010-y", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045933948"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-94-009-7798-3_5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048349248", 
          "https://doi.org/10.1007/978-94-009-7798-3_5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0166-218x(93)90012-d", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052359637"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0406014", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062844757"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0608024", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062850112"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.4153/cjm-1964-055-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1072264594"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1994-03", 
    "datePublishedReg": "1994-03-01", 
    "description": "We show that the pathwidth of a cocomparability graphG equals its treewidth. The proof is based on a new notion, calledinterval width, for a partial orderP, which is the smallest width of an interval order contained inP, and which is shown to be equal to the treewidth of its cocomparability graph. We observe also that determining any of these parameters isNP-hard and we establish some connections between classical dimension notions of partial orders and interval width. In fact we develop approximation algorithms for interval width ofP whose performance ratios depend on the dimension and interval dimension ofP, respectively.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf01462229", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136683", 
        "issn": [
          "0167-8094", 
          "1572-9273"
        ], 
        "name": "Order", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "11"
      }
    ], 
    "name": "Treewidth of cocomparability graphs and a new order-theoretic parameter", 
    "pagination": "47-60", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "4132d04eec7e43fa9e53e2b399bb421a7a2c8b13eb729945a65d85f0bfd0a61c"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01462229"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1013686190"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01462229", 
      "https://app.dimensions.ai/details/publication/pub.1013686190"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T13:26", 
    "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/0000000370_0000000370/records_46737_00000000.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/BF01462229"
  }
]
 

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/bf01462229'

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/bf01462229'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf01462229'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf01462229'


 

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

109 TRIPLES      21 PREDICATES      38 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01462229 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N953396a0d0dd4e8dab3689ec58463ce2
4 schema:citation sg:pub.10.1007/978-3-642-46908-4_70
5 sg:pub.10.1007/978-3-7091-9076-0_2
6 sg:pub.10.1007/978-94-009-2639-4_4
7 sg:pub.10.1007/978-94-009-7798-3_5
8 sg:pub.10.1007/bf01934985
9 https://doi.org/10.1016/0012-365x(91)90010-y
10 https://doi.org/10.1016/0166-218x(93)90012-d
11 https://doi.org/10.1016/s0304-0208(08)73832-5
12 https://doi.org/10.1137/0406014
13 https://doi.org/10.1137/0608024
14 https://doi.org/10.4153/cjm-1964-055-5
15 schema:datePublished 1994-03
16 schema:datePublishedReg 1994-03-01
17 schema:description We show that the pathwidth of a cocomparability graphG equals its treewidth. The proof is based on a new notion, calledinterval width, for a partial orderP, which is the smallest width of an interval order contained inP, and which is shown to be equal to the treewidth of its cocomparability graph. We observe also that determining any of these parameters isNP-hard and we establish some connections between classical dimension notions of partial orders and interval width. In fact we develop approximation algorithms for interval width ofP whose performance ratios depend on the dimension and interval dimension ofP, respectively.
18 schema:genre research_article
19 schema:inLanguage en
20 schema:isAccessibleForFree false
21 schema:isPartOf N53b4be5f37c340cb98e2118545f3f2cb
22 Nf69228a8094846559844cea0344d1703
23 sg:journal.1136683
24 schema:name Treewidth of cocomparability graphs and a new order-theoretic parameter
25 schema:pagination 47-60
26 schema:productId N04f5703be7844420af941683258de1ae
27 N8535c51a83dc487eba4fa132ff12b4f9
28 Nfa91adb5292443148cf56a142448106c
29 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013686190
30 https://doi.org/10.1007/bf01462229
31 schema:sdDatePublished 2019-04-11T13:26
32 schema:sdLicense https://scigraph.springernature.com/explorer/license/
33 schema:sdPublisher Nc044da686a134e50a6ece44bea1b6572
34 schema:url http://link.springer.com/10.1007/BF01462229
35 sgo:license sg:explorer/license/
36 sgo:sdDataset articles
37 rdf:type schema:ScholarlyArticle
38 N04f5703be7844420af941683258de1ae schema:name readcube_id
39 schema:value 4132d04eec7e43fa9e53e2b399bb421a7a2c8b13eb729945a65d85f0bfd0a61c
40 rdf:type schema:PropertyValue
41 N53b4be5f37c340cb98e2118545f3f2cb schema:volumeNumber 11
42 rdf:type schema:PublicationVolume
43 N8535c51a83dc487eba4fa132ff12b4f9 schema:name dimensions_id
44 schema:value pub.1013686190
45 rdf:type schema:PropertyValue
46 N8d03c4e7d4424854a85d82c65cdad6a2 rdf:first sg:person.011470250675.54
47 rdf:rest rdf:nil
48 N953396a0d0dd4e8dab3689ec58463ce2 rdf:first sg:person.012600773121.44
49 rdf:rest N8d03c4e7d4424854a85d82c65cdad6a2
50 Nc044da686a134e50a6ece44bea1b6572 schema:name Springer Nature - SN SciGraph project
51 rdf:type schema:Organization
52 Nf69228a8094846559844cea0344d1703 schema:issueNumber 1
53 rdf:type schema:PublicationIssue
54 Nfa91adb5292443148cf56a142448106c schema:name doi
55 schema:value 10.1007/bf01462229
56 rdf:type schema:PropertyValue
57 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
58 schema:name Information and Computing Sciences
59 rdf:type schema:DefinedTerm
60 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
61 schema:name Computation Theory and Mathematics
62 rdf:type schema:DefinedTerm
63 sg:journal.1136683 schema:issn 0167-8094
64 1572-9273
65 schema:name Order
66 rdf:type schema:Periodical
67 sg:person.011470250675.54 schema:affiliation https://www.grid.ac/institutes/grid.6734.6
68 schema:familyName Möhring
69 schema:givenName Rolf H.
70 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011470250675.54
71 rdf:type schema:Person
72 sg:person.012600773121.44 schema:affiliation https://www.grid.ac/institutes/grid.464638.b
73 schema:familyName Habib
74 schema:givenName Michel
75 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012600773121.44
76 rdf:type schema:Person
77 sg:pub.10.1007/978-3-642-46908-4_70 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037858395
78 https://doi.org/10.1007/978-3-642-46908-4_70
79 rdf:type schema:CreativeWork
80 sg:pub.10.1007/978-3-7091-9076-0_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012939792
81 https://doi.org/10.1007/978-3-7091-9076-0_2
82 rdf:type schema:CreativeWork
83 sg:pub.10.1007/978-94-009-2639-4_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012529275
84 https://doi.org/10.1007/978-94-009-2639-4_4
85 rdf:type schema:CreativeWork
86 sg:pub.10.1007/978-94-009-7798-3_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048349248
87 https://doi.org/10.1007/978-94-009-7798-3_5
88 rdf:type schema:CreativeWork
89 sg:pub.10.1007/bf01934985 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001971810
90 https://doi.org/10.1007/bf01934985
91 rdf:type schema:CreativeWork
92 https://doi.org/10.1016/0012-365x(91)90010-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1045933948
93 rdf:type schema:CreativeWork
94 https://doi.org/10.1016/0166-218x(93)90012-d schema:sameAs https://app.dimensions.ai/details/publication/pub.1052359637
95 rdf:type schema:CreativeWork
96 https://doi.org/10.1016/s0304-0208(08)73832-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036569865
97 rdf:type schema:CreativeWork
98 https://doi.org/10.1137/0406014 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062844757
99 rdf:type schema:CreativeWork
100 https://doi.org/10.1137/0608024 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062850112
101 rdf:type schema:CreativeWork
102 https://doi.org/10.4153/cjm-1964-055-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072264594
103 rdf:type schema:CreativeWork
104 https://www.grid.ac/institutes/grid.464638.b schema:alternateName Montpellier Laboratory of Informatics, Robotics and Microelectronics
105 schema:name LIRMM, 161 rue Ada, 34392, Montpellier, France
106 rdf:type schema:Organization
107 https://www.grid.ac/institutes/grid.6734.6 schema:alternateName Technical University of Berlin
108 schema:name Fachbereich Mathematik, Technische Universität Berlin, 1000, Berlin 12, Germany
109 rdf:type schema:Organization
 




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


...