NP-completeness properties about linear extensions View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1987-06

AUTHORS

Vincent Bouchitte, Michel Habib

ABSTRACT

Following the pioneering work of Kierstead, we present here some complexity results about the construction of depth-first greedy linear extensions. We prove that the recognition of Dilworth partially ordered sets of height 2, as defined by Syslo, is NP-complete. This last result yields a new proof of the NP-completeness of the jump number problem, first proved by Pulleyblank. More... »

PAGES

143-154

References to SciGraph publications

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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": "Mines Saint-Etienne", 
          "id": "https://www.grid.ac/institutes/grid.424462.2", 
          "name": [
            "D\u00e9partement Informatique Appliqu\u00e9e, Ecole des Mines de Saint-Etienne, 158 cours Fauriel, 42023, Saint-Etienne cedex 2, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bouchitte", 
        "givenName": "Vincent", 
        "id": "sg:person.015321110747.72", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015321110747.72"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IMT Atlantique", 
          "id": "https://www.grid.ac/institutes/grid.486295.4", 
          "name": [
            "LIB (Laboratoire commun ENST Br et UBO), D\u00e9partement Informatique et R\u00e9seaux, Ecole Nationale Sup\u00e9rieure des T\u00e9l\u00e9communications de Bretagne, ZI de Kernevent, BP 832, 29285, Brest cedex, 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"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1090/s0002-9939-1983-0715851-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023986109"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00390103", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028574857", 
          "https://doi.org/10.1007/bf00390103"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00390103", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028574857", 
          "https://doi.org/10.1007/bf00390103"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00390103", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028574857", 
          "https://doi.org/10.1007/bf00390103"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/s0002-9939-1982-0660592-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046677743"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/800157.805047", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053230526"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0214068", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841857"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0603036", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062848761"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.2307/1969503", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1069674881"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1051/ita/1979130100031", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1083712844"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1987-06", 
    "datePublishedReg": "1987-06-01", 
    "description": "Following the pioneering work of Kierstead, we present here some complexity results about the construction of depth-first greedy linear extensions. We prove that the recognition of Dilworth partially ordered sets of height 2, as defined by Syslo, is NP-complete. This last result yields a new proof of the NP-completeness of the jump number problem, first proved by Pulleyblank.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf00337693", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136683", 
        "issn": [
          "0167-8094", 
          "1572-9273"
        ], 
        "name": "Order", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "4"
      }
    ], 
    "name": "NP-completeness properties about linear extensions", 
    "pagination": "143-154", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf00337693"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "b2067fcecf4521c22ef7da6e0722450ca74057d0e8d7ce80191b7f52588e9d58"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1037372102"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf00337693", 
      "https://app.dimensions.ai/details/publication/pub.1037372102"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-15T08:48", 
    "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/0000000374_0000000374/records_119717_00000000.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/BF00337693"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

96 TRIPLES      21 PREDICATES      35 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf00337693 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nfe6942ddfb024519b82e075d86efbfa4
4 schema:citation sg:pub.10.1007/bf00390103
5 https://doi.org/10.1051/ita/1979130100031
6 https://doi.org/10.1090/s0002-9939-1982-0660592-3
7 https://doi.org/10.1090/s0002-9939-1983-0715851-3
8 https://doi.org/10.1137/0214068
9 https://doi.org/10.1137/0603036
10 https://doi.org/10.1145/800157.805047
11 https://doi.org/10.2307/1969503
12 schema:datePublished 1987-06
13 schema:datePublishedReg 1987-06-01
14 schema:description Following the pioneering work of Kierstead, we present here some complexity results about the construction of depth-first greedy linear extensions. We prove that the recognition of Dilworth partially ordered sets of height 2, as defined by Syslo, is NP-complete. This last result yields a new proof of the NP-completeness of the jump number problem, first proved by Pulleyblank.
15 schema:genre research_article
16 schema:inLanguage en
17 schema:isAccessibleForFree false
18 schema:isPartOf N0af869ccea404a1fa2271d61d0c54f84
19 N3c389c2bf3e34978a7d54ce2ffd25fe6
20 sg:journal.1136683
21 schema:name NP-completeness properties about linear extensions
22 schema:pagination 143-154
23 schema:productId N5636e500f25d430bbadd8a2786352a6c
24 Nd75d064b2e754da8a1fe06d807421c3a
25 Ndc06c6cf504546e592417510b5397140
26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037372102
27 https://doi.org/10.1007/bf00337693
28 schema:sdDatePublished 2019-04-15T08:48
29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
30 schema:sdPublisher Nce31693926894cda896d8f796d45c6d5
31 schema:url http://link.springer.com/10.1007/BF00337693
32 sgo:license sg:explorer/license/
33 sgo:sdDataset articles
34 rdf:type schema:ScholarlyArticle
35 N0af869ccea404a1fa2271d61d0c54f84 schema:issueNumber 2
36 rdf:type schema:PublicationIssue
37 N22ffd12cd86c49559e75fb0061fb23a8 rdf:first sg:person.012600773121.44
38 rdf:rest rdf:nil
39 N3c389c2bf3e34978a7d54ce2ffd25fe6 schema:volumeNumber 4
40 rdf:type schema:PublicationVolume
41 N5636e500f25d430bbadd8a2786352a6c schema:name dimensions_id
42 schema:value pub.1037372102
43 rdf:type schema:PropertyValue
44 Nce31693926894cda896d8f796d45c6d5 schema:name Springer Nature - SN SciGraph project
45 rdf:type schema:Organization
46 Nd75d064b2e754da8a1fe06d807421c3a schema:name readcube_id
47 schema:value b2067fcecf4521c22ef7da6e0722450ca74057d0e8d7ce80191b7f52588e9d58
48 rdf:type schema:PropertyValue
49 Ndc06c6cf504546e592417510b5397140 schema:name doi
50 schema:value 10.1007/bf00337693
51 rdf:type schema:PropertyValue
52 Nfe6942ddfb024519b82e075d86efbfa4 rdf:first sg:person.015321110747.72
53 rdf:rest N22ffd12cd86c49559e75fb0061fb23a8
54 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
55 schema:name Information and Computing Sciences
56 rdf:type schema:DefinedTerm
57 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
58 schema:name Computation Theory and Mathematics
59 rdf:type schema:DefinedTerm
60 sg:journal.1136683 schema:issn 0167-8094
61 1572-9273
62 schema:name Order
63 rdf:type schema:Periodical
64 sg:person.012600773121.44 schema:affiliation https://www.grid.ac/institutes/grid.486295.4
65 schema:familyName Habib
66 schema:givenName Michel
67 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012600773121.44
68 rdf:type schema:Person
69 sg:person.015321110747.72 schema:affiliation https://www.grid.ac/institutes/grid.424462.2
70 schema:familyName Bouchitte
71 schema:givenName Vincent
72 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015321110747.72
73 rdf:type schema:Person
74 sg:pub.10.1007/bf00390103 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028574857
75 https://doi.org/10.1007/bf00390103
76 rdf:type schema:CreativeWork
77 https://doi.org/10.1051/ita/1979130100031 schema:sameAs https://app.dimensions.ai/details/publication/pub.1083712844
78 rdf:type schema:CreativeWork
79 https://doi.org/10.1090/s0002-9939-1982-0660592-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046677743
80 rdf:type schema:CreativeWork
81 https://doi.org/10.1090/s0002-9939-1983-0715851-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023986109
82 rdf:type schema:CreativeWork
83 https://doi.org/10.1137/0214068 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841857
84 rdf:type schema:CreativeWork
85 https://doi.org/10.1137/0603036 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062848761
86 rdf:type schema:CreativeWork
87 https://doi.org/10.1145/800157.805047 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053230526
88 rdf:type schema:CreativeWork
89 https://doi.org/10.2307/1969503 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069674881
90 rdf:type schema:CreativeWork
91 https://www.grid.ac/institutes/grid.424462.2 schema:alternateName Mines Saint-Etienne
92 schema:name Département Informatique Appliquée, Ecole des Mines de Saint-Etienne, 158 cours Fauriel, 42023, Saint-Etienne cedex 2, France
93 rdf:type schema:Organization
94 https://www.grid.ac/institutes/grid.486295.4 schema:alternateName IMT Atlantique
95 schema:name LIB (Laboratoire commun ENST Br et UBO), Département Informatique et Réseaux, Ecole Nationale Supérieure des Télécommunications de Bretagne, ZI de Kernevent, BP 832, 29285, Brest cedex, France
96 rdf:type schema:Organization
 




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


...