Implementing branch-and-bound in a ring of processors View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1986

AUTHORS

Oliver Vornberger

ABSTRACT

A set of personal computers is connected to form a ring structured parallel system: Each processor has access to its local memory and can exchange messages with its two ring neighbors. A branch-and-bound procedure is implemented in Pascal to run in parallel on the ring and solve the Travelling-Salesman-Problem. Heuristics are developed to maintain a priority queue in a distributed heap. The computing times and speedups for 25 random graphs obtained with up to 16 ring members are discussed. More... »

PAGES

157-164

References to SciGraph publications

Book

TITLE

CONPAR 86

ISBN

978-3-540-16811-9
978-3-540-44856-3

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-16811-7_166

DOI

http://dx.doi.org/10.1007/3-540-16811-7_166

DIMENSIONS

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


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/0803", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computer Software", 
        "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 Paderborn", 
          "id": "https://www.grid.ac/institutes/grid.5659.f", 
          "name": [
            "Dept. of Mathematics & Computer Science, University of Paderborn, West \u2014 Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vornberger", 
        "givenName": "Oliver", 
        "id": "sg:person.012144130473.77", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012144130473.77"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/358080.358103", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017244639"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/22719.24067", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1029110657"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01584070", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044774302", 
          "https://doi.org/10.1007/bf01584070"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1986", 
    "datePublishedReg": "1986-01-01", 
    "description": "A set of personal computers is connected to form a ring structured parallel system: Each processor has access to its local memory and can exchange messages with its two ring neighbors. A branch-and-bound procedure is implemented in Pascal to run in parallel on the ring and solve the Travelling-Salesman-Problem. Heuristics are developed to maintain a priority queue in a distributed heap. The computing times and speedups for 25 random graphs obtained with up to 16 ring members are discussed.", 
    "editor": [
      {
        "familyName": "H\u00e4ndler", 
        "givenName": "Wolfgang", 
        "type": "Person"
      }, 
      {
        "familyName": "Haupt", 
        "givenName": "Dieter", 
        "type": "Person"
      }, 
      {
        "familyName": "Jeltsch", 
        "givenName": "Rolf", 
        "type": "Person"
      }, 
      {
        "familyName": "Juling", 
        "givenName": "Wilfried", 
        "type": "Person"
      }, 
      {
        "familyName": "Lange", 
        "givenName": "Otto", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-16811-7_166", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-16811-9", 
        "978-3-540-44856-3"
      ], 
      "name": "CONPAR 86", 
      "type": "Book"
    }, 
    "name": "Implementing branch-and-bound in a ring of processors", 
    "pagination": "157-164", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-16811-7_166"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "6c5ab0e00e55547fdd6be4497a1525f189c73a5552411021063337ef8096da86"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1022743669"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-16811-7_166", 
      "https://app.dimensions.ai/details/publication/pub.1022743669"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T23:51", 
    "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_8697_00000257.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-16811-7_166"
  }
]
 

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-16811-7_166'

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-16811-7_166'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-16811-7_166'

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-16811-7_166'


 

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

95 TRIPLES      23 PREDICATES      30 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-16811-7_166 schema:about anzsrc-for:08
2 anzsrc-for:0803
3 schema:author N3ab6e30711c34924aaa9756eea00c5c3
4 schema:citation sg:pub.10.1007/bf01584070
5 https://doi.org/10.1145/22719.24067
6 https://doi.org/10.1145/358080.358103
7 schema:datePublished 1986
8 schema:datePublishedReg 1986-01-01
9 schema:description A set of personal computers is connected to form a ring structured parallel system: Each processor has access to its local memory and can exchange messages with its two ring neighbors. A branch-and-bound procedure is implemented in Pascal to run in parallel on the ring and solve the Travelling-Salesman-Problem. Heuristics are developed to maintain a priority queue in a distributed heap. The computing times and speedups for 25 random graphs obtained with up to 16 ring members are discussed.
10 schema:editor Nbd6f5afae50544f7ba8b7c493477fd0b
11 schema:genre chapter
12 schema:inLanguage en
13 schema:isAccessibleForFree false
14 schema:isPartOf Ncb7aa973e37c4a4ab1107ba328f8ff73
15 schema:name Implementing branch-and-bound in a ring of processors
16 schema:pagination 157-164
17 schema:productId N4b4e3aeff5ec4f87909025de205e3ef4
18 N68c62373f5e94461ae74e3008665710f
19 N9be5f1aa31784ca38f5cc90fcdd287b6
20 schema:publisher N4cabe3e5bd154f8cac08e9f76b60e615
21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022743669
22 https://doi.org/10.1007/3-540-16811-7_166
23 schema:sdDatePublished 2019-04-15T23:51
24 schema:sdLicense https://scigraph.springernature.com/explorer/license/
25 schema:sdPublisher Naf532b9757524450829e2d3389bfa8a9
26 schema:url http://link.springer.com/10.1007/3-540-16811-7_166
27 sgo:license sg:explorer/license/
28 sgo:sdDataset chapters
29 rdf:type schema:Chapter
30 N1639125512314b95a29561a970cd3f88 schema:familyName Jeltsch
31 schema:givenName Rolf
32 rdf:type schema:Person
33 N3ab6e30711c34924aaa9756eea00c5c3 rdf:first sg:person.012144130473.77
34 rdf:rest rdf:nil
35 N4372ddcbceb7467281b249ad288847c6 schema:familyName Juling
36 schema:givenName Wilfried
37 rdf:type schema:Person
38 N4b4e3aeff5ec4f87909025de205e3ef4 schema:name dimensions_id
39 schema:value pub.1022743669
40 rdf:type schema:PropertyValue
41 N4cabe3e5bd154f8cac08e9f76b60e615 schema:location Berlin, Heidelberg
42 schema:name Springer Berlin Heidelberg
43 rdf:type schema:Organisation
44 N68c62373f5e94461ae74e3008665710f schema:name doi
45 schema:value 10.1007/3-540-16811-7_166
46 rdf:type schema:PropertyValue
47 N7360214a666e4c2fa11baeedbe258bc9 schema:familyName Haupt
48 schema:givenName Dieter
49 rdf:type schema:Person
50 N7ae0655fca83407b893aa2756ba326ec rdf:first N1639125512314b95a29561a970cd3f88
51 rdf:rest Na24c00d1a5a64c539f8547458c4b73fe
52 N8d0bf4ee08ae49dab2b8cd22b2baf1b7 rdf:first Nb3809666895f4debb105aa664831ac01
53 rdf:rest rdf:nil
54 N9be5f1aa31784ca38f5cc90fcdd287b6 schema:name readcube_id
55 schema:value 6c5ab0e00e55547fdd6be4497a1525f189c73a5552411021063337ef8096da86
56 rdf:type schema:PropertyValue
57 Na24c00d1a5a64c539f8547458c4b73fe rdf:first N4372ddcbceb7467281b249ad288847c6
58 rdf:rest N8d0bf4ee08ae49dab2b8cd22b2baf1b7
59 Naf532b9757524450829e2d3389bfa8a9 schema:name Springer Nature - SN SciGraph project
60 rdf:type schema:Organization
61 Nb3809666895f4debb105aa664831ac01 schema:familyName Lange
62 schema:givenName Otto
63 rdf:type schema:Person
64 Nb4ffc41bbb174e88924eae8c11a09c48 rdf:first N7360214a666e4c2fa11baeedbe258bc9
65 rdf:rest N7ae0655fca83407b893aa2756ba326ec
66 Nbd6f5afae50544f7ba8b7c493477fd0b rdf:first Nc9d5ad201f54471da20e34bb336f3cdd
67 rdf:rest Nb4ffc41bbb174e88924eae8c11a09c48
68 Nc9d5ad201f54471da20e34bb336f3cdd schema:familyName Händler
69 schema:givenName Wolfgang
70 rdf:type schema:Person
71 Ncb7aa973e37c4a4ab1107ba328f8ff73 schema:isbn 978-3-540-16811-9
72 978-3-540-44856-3
73 schema:name CONPAR 86
74 rdf:type schema:Book
75 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
76 schema:name Information and Computing Sciences
77 rdf:type schema:DefinedTerm
78 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
79 schema:name Computer Software
80 rdf:type schema:DefinedTerm
81 sg:person.012144130473.77 schema:affiliation https://www.grid.ac/institutes/grid.5659.f
82 schema:familyName Vornberger
83 schema:givenName Oliver
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012144130473.77
85 rdf:type schema:Person
86 sg:pub.10.1007/bf01584070 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044774302
87 https://doi.org/10.1007/bf01584070
88 rdf:type schema:CreativeWork
89 https://doi.org/10.1145/22719.24067 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029110657
90 rdf:type schema:CreativeWork
91 https://doi.org/10.1145/358080.358103 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017244639
92 rdf:type schema:CreativeWork
93 https://www.grid.ac/institutes/grid.5659.f schema:alternateName University of Paderborn
94 schema:name Dept. of Mathematics & Computer Science, University of Paderborn, West — Germany
95 rdf:type schema:Organization
 




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


...