Graphical Data Structures for Ordered Sets View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1989

AUTHORS

Ivan Rival

ABSTRACT

Ordered sets occur widely in computation, in scheduling, in sorting, in social choice, and even in geography. For some years research on these themes has focussed first on combinatorial optimization and then on “algorithmics”. Important advances have been made both at practical and, at theoretical levels. There is little doubt that the modern mathematical theory of ordered sets owes much of its vitality to these recent developments. While some of the problems remain exceedingly difficult, such as the “three-machine scheduling problem”, attention is shifting from the usual optimization themes to data structures; indeed, there is emerging a need for efficient data structures to code and store ordered sets. Among these data structures, graphical ones are coming to play a decisive role, for instance, in problems in which decisions must be made from among alternatives ranked according to precedence or preference relations. More... »

PAGES

3-31

Book

TITLE

Algorithms and Order

ISBN

978-94-010-7691-3
978-94-009-2639-4

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-94-009-2639-4_1

DOI

http://dx.doi.org/10.1007/978-94-009-2639-4_1

DIMENSIONS

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


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 Ottawa", 
          "id": "https://www.grid.ac/institutes/grid.28046.38", 
          "name": [
            "Department of Computer Science, The University of Ottawa, Ottawa, Ontario, Canada, K1N 6N5"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rival", 
        "givenName": "Ivan", 
        "id": "sg:person.013152666767.29", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013152666767.29"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf02020961", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005931527", 
          "https://doi.org/10.1007/bf02020961"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02020961", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005931527", 
          "https://doi.org/10.1007/bf02020961"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00340774", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016464666", 
          "https://doi.org/10.1007/bf00340774"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00340774", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016464666", 
          "https://doi.org/10.1007/bf00340774"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0012-365x(81)90201-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017851492"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00383600", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019618891", 
          "https://doi.org/10.1007/bf00383600"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00383600", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019618891", 
          "https://doi.org/10.1007/bf00383600"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/321850.321852", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023277958"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/net.3230020103", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024275235"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0095-8956(76)90024-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025374458"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0012-365x(87)90008-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027243701"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00714475", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027631133", 
          "https://doi.org/10.1007/bf00714475"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00714475", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027631133", 
          "https://doi.org/10.1007/bf00714475"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00337921", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034514624", 
          "https://doi.org/10.1007/bf00337921"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00337921", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034514624", 
          "https://doi.org/10.1007/bf00337921"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00390104", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039198624", 
          "https://doi.org/10.1007/bf00390104"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00390104", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039198624", 
          "https://doi.org/10.1007/bf00390104"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00390104", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039198624", 
          "https://doi.org/10.1007/bf00390104"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/s0002-9939-1983-0695239-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043584204"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/jgt.3190080407", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044572706"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0216030", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841976"
        ], 
        "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.2307/2690292", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1070062087"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.4153/cjm-1975-074-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1072266040"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.4153/cjm-1977-040-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1072266282"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1989", 
    "datePublishedReg": "1989-01-01", 
    "description": "Ordered sets occur widely in computation, in scheduling, in sorting, in social choice, and even in geography. For some years research on these themes has focussed first on combinatorial optimization and then on \u201calgorithmics\u201d. Important advances have been made both at practical and, at theoretical levels. There is little doubt that the modern mathematical theory of ordered sets owes much of its vitality to these recent developments. While some of the problems remain exceedingly difficult, such as the \u201cthree-machine scheduling problem\u201d, attention is shifting from the usual optimization themes to data structures; indeed, there is emerging a need for efficient data structures to code and store ordered sets. Among these data structures, graphical ones are coming to play a decisive role, for instance, in problems in which decisions must be made from among alternatives ranked according to precedence or preference relations.", 
    "editor": [
      {
        "familyName": "Rival", 
        "givenName": "Ivan", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-94-009-2639-4_1", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-94-010-7691-3", 
        "978-94-009-2639-4"
      ], 
      "name": "Algorithms and Order", 
      "type": "Book"
    }, 
    "name": "Graphical Data Structures for Ordered Sets", 
    "pagination": "3-31", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-94-009-2639-4_1"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "19b413fb3d6453b6cb9e6d9626f4d4ef3e4b34f238f1d123c6a44b386f270106"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1005395011"
        ]
      }
    ], 
    "publisher": {
      "location": "Dordrecht", 
      "name": "Springer Netherlands", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-94-009-2639-4_1", 
      "https://app.dimensions.ai/details/publication/pub.1005395011"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T20:59", 
    "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_8690_00000246.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-94-009-2639-4_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/978-94-009-2639-4_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/978-94-009-2639-4_1'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-94-009-2639-4_1'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-94-009-2639-4_1'


 

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

125 TRIPLES      23 PREDICATES      45 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-94-009-2639-4_1 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N5a40ebca9de9404dbea7352db302a4b9
4 schema:citation sg:pub.10.1007/bf00337921
5 sg:pub.10.1007/bf00340774
6 sg:pub.10.1007/bf00383600
7 sg:pub.10.1007/bf00390104
8 sg:pub.10.1007/bf00714475
9 sg:pub.10.1007/bf02020961
10 https://doi.org/10.1002/jgt.3190080407
11 https://doi.org/10.1002/net.3230020103
12 https://doi.org/10.1016/0012-365x(81)90201-6
13 https://doi.org/10.1016/0012-365x(87)90008-2
14 https://doi.org/10.1016/0095-8956(76)90024-1
15 https://doi.org/10.1090/s0002-9939-1983-0695239-4
16 https://doi.org/10.1137/0216030
17 https://doi.org/10.1145/321850.321852
18 https://doi.org/10.2307/1969503
19 https://doi.org/10.2307/2690292
20 https://doi.org/10.4153/cjm-1975-074-0
21 https://doi.org/10.4153/cjm-1977-040-3
22 schema:datePublished 1989
23 schema:datePublishedReg 1989-01-01
24 schema:description Ordered sets occur widely in computation, in scheduling, in sorting, in social choice, and even in geography. For some years research on these themes has focussed first on combinatorial optimization and then on “algorithmics”. Important advances have been made both at practical and, at theoretical levels. There is little doubt that the modern mathematical theory of ordered sets owes much of its vitality to these recent developments. While some of the problems remain exceedingly difficult, such as the “three-machine scheduling problem”, attention is shifting from the usual optimization themes to data structures; indeed, there is emerging a need for efficient data structures to code and store ordered sets. Among these data structures, graphical ones are coming to play a decisive role, for instance, in problems in which decisions must be made from among alternatives ranked according to precedence or preference relations.
25 schema:editor Nbd7dbf7118564b76a118130ea6e29959
26 schema:genre chapter
27 schema:inLanguage en
28 schema:isAccessibleForFree false
29 schema:isPartOf Nbbdf84778d464bffb0b7379da983ca1e
30 schema:name Graphical Data Structures for Ordered Sets
31 schema:pagination 3-31
32 schema:productId N4f0f863be4d04eb9b6d6b4d3b1f88aaa
33 Nb10dd048d611481aa5969aa4fd24edac
34 Nf7f9d0fa13c04b22b7047629bc963e84
35 schema:publisher N37bf799cc4c64b349bd63c6ac878b753
36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005395011
37 https://doi.org/10.1007/978-94-009-2639-4_1
38 schema:sdDatePublished 2019-04-15T20:59
39 schema:sdLicense https://scigraph.springernature.com/explorer/license/
40 schema:sdPublisher N2a9e98048fa14cbaa3ee9f2d937922cf
41 schema:url http://link.springer.com/10.1007/978-94-009-2639-4_1
42 sgo:license sg:explorer/license/
43 sgo:sdDataset chapters
44 rdf:type schema:Chapter
45 N028c058b1d4e4cdbbfed6dde964a7ff9 schema:familyName Rival
46 schema:givenName Ivan
47 rdf:type schema:Person
48 N2a9e98048fa14cbaa3ee9f2d937922cf schema:name Springer Nature - SN SciGraph project
49 rdf:type schema:Organization
50 N37bf799cc4c64b349bd63c6ac878b753 schema:location Dordrecht
51 schema:name Springer Netherlands
52 rdf:type schema:Organisation
53 N4f0f863be4d04eb9b6d6b4d3b1f88aaa schema:name readcube_id
54 schema:value 19b413fb3d6453b6cb9e6d9626f4d4ef3e4b34f238f1d123c6a44b386f270106
55 rdf:type schema:PropertyValue
56 N5a40ebca9de9404dbea7352db302a4b9 rdf:first sg:person.013152666767.29
57 rdf:rest rdf:nil
58 Nb10dd048d611481aa5969aa4fd24edac schema:name doi
59 schema:value 10.1007/978-94-009-2639-4_1
60 rdf:type schema:PropertyValue
61 Nbbdf84778d464bffb0b7379da983ca1e schema:isbn 978-94-009-2639-4
62 978-94-010-7691-3
63 schema:name Algorithms and Order
64 rdf:type schema:Book
65 Nbd7dbf7118564b76a118130ea6e29959 rdf:first N028c058b1d4e4cdbbfed6dde964a7ff9
66 rdf:rest rdf:nil
67 Nf7f9d0fa13c04b22b7047629bc963e84 schema:name dimensions_id
68 schema:value pub.1005395011
69 rdf:type schema:PropertyValue
70 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
71 schema:name Information and Computing Sciences
72 rdf:type schema:DefinedTerm
73 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
74 schema:name Computation Theory and Mathematics
75 rdf:type schema:DefinedTerm
76 sg:person.013152666767.29 schema:affiliation https://www.grid.ac/institutes/grid.28046.38
77 schema:familyName Rival
78 schema:givenName Ivan
79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013152666767.29
80 rdf:type schema:Person
81 sg:pub.10.1007/bf00337921 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034514624
82 https://doi.org/10.1007/bf00337921
83 rdf:type schema:CreativeWork
84 sg:pub.10.1007/bf00340774 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016464666
85 https://doi.org/10.1007/bf00340774
86 rdf:type schema:CreativeWork
87 sg:pub.10.1007/bf00383600 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019618891
88 https://doi.org/10.1007/bf00383600
89 rdf:type schema:CreativeWork
90 sg:pub.10.1007/bf00390104 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039198624
91 https://doi.org/10.1007/bf00390104
92 rdf:type schema:CreativeWork
93 sg:pub.10.1007/bf00714475 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027631133
94 https://doi.org/10.1007/bf00714475
95 rdf:type schema:CreativeWork
96 sg:pub.10.1007/bf02020961 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005931527
97 https://doi.org/10.1007/bf02020961
98 rdf:type schema:CreativeWork
99 https://doi.org/10.1002/jgt.3190080407 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044572706
100 rdf:type schema:CreativeWork
101 https://doi.org/10.1002/net.3230020103 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024275235
102 rdf:type schema:CreativeWork
103 https://doi.org/10.1016/0012-365x(81)90201-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017851492
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1016/0012-365x(87)90008-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027243701
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1016/0095-8956(76)90024-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025374458
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1090/s0002-9939-1983-0695239-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043584204
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1137/0216030 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841976
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1145/321850.321852 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023277958
114 rdf:type schema:CreativeWork
115 https://doi.org/10.2307/1969503 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069674881
116 rdf:type schema:CreativeWork
117 https://doi.org/10.2307/2690292 schema:sameAs https://app.dimensions.ai/details/publication/pub.1070062087
118 rdf:type schema:CreativeWork
119 https://doi.org/10.4153/cjm-1975-074-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072266040
120 rdf:type schema:CreativeWork
121 https://doi.org/10.4153/cjm-1977-040-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1072266282
122 rdf:type schema:CreativeWork
123 https://www.grid.ac/institutes/grid.28046.38 schema:alternateName University of Ottawa
124 schema:name Department of Computer Science, The University of Ottawa, Ottawa, Ontario, Canada, K1N 6N5
125 rdf:type schema:Organization
 




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


...