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 Ne64f5eda634646bf9cfb1a0f80807927
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 N26af97bcdc9047929d513869a55d0235
11 schema:genre chapter
12 schema:inLanguage en
13 schema:isAccessibleForFree false
14 schema:isPartOf N870257c2a6fb4c5bac802d19daaf9468
15 schema:name Implementing branch-and-bound in a ring of processors
16 schema:pagination 157-164
17 schema:productId N1ab7481bdfd04050b92e0c0bcfcf81ba
18 N5b304f362be54781af36959d73e05fd6
19 Nb9ebed702e9b4348b9e4429da0cd048f
20 schema:publisher Na88a0700bf9b44ccbbac95202faa123b
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 Nc7025483cf5e48f7b6241233812c3c33
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 N0bb4ea57578d4a2881e1d58cfbbc8792 schema:familyName Juling
31 schema:givenName Wilfried
32 rdf:type schema:Person
33 N13001397216f497d9587ff03f1954d20 schema:familyName Händler
34 schema:givenName Wolfgang
35 rdf:type schema:Person
36 N1ab7481bdfd04050b92e0c0bcfcf81ba schema:name doi
37 schema:value 10.1007/3-540-16811-7_166
38 rdf:type schema:PropertyValue
39 N26af97bcdc9047929d513869a55d0235 rdf:first N13001397216f497d9587ff03f1954d20
40 rdf:rest Nb57f83f5fae644a38e505910ff9789c7
41 N3d276b7faa5f475c926fe9b644121801 rdf:first N8305b25f490d4562a549c3be419ee722
42 rdf:rest Nd074e9b1e3e24bae941bb2bc2f3e6aa2
43 N5b304f362be54781af36959d73e05fd6 schema:name dimensions_id
44 schema:value pub.1022743669
45 rdf:type schema:PropertyValue
46 N7987c9ed36304232bf881b9346527eeb schema:familyName Haupt
47 schema:givenName Dieter
48 rdf:type schema:Person
49 N8305b25f490d4562a549c3be419ee722 schema:familyName Jeltsch
50 schema:givenName Rolf
51 rdf:type schema:Person
52 N870257c2a6fb4c5bac802d19daaf9468 schema:isbn 978-3-540-16811-9
53 978-3-540-44856-3
54 schema:name CONPAR 86
55 rdf:type schema:Book
56 Na88a0700bf9b44ccbbac95202faa123b schema:location Berlin, Heidelberg
57 schema:name Springer Berlin Heidelberg
58 rdf:type schema:Organisation
59 Nb57f83f5fae644a38e505910ff9789c7 rdf:first N7987c9ed36304232bf881b9346527eeb
60 rdf:rest N3d276b7faa5f475c926fe9b644121801
61 Nb9ebed702e9b4348b9e4429da0cd048f schema:name readcube_id
62 schema:value 6c5ab0e00e55547fdd6be4497a1525f189c73a5552411021063337ef8096da86
63 rdf:type schema:PropertyValue
64 Nc7025483cf5e48f7b6241233812c3c33 schema:name Springer Nature - SN SciGraph project
65 rdf:type schema:Organization
66 Nd074e9b1e3e24bae941bb2bc2f3e6aa2 rdf:first N0bb4ea57578d4a2881e1d58cfbbc8792
67 rdf:rest Ne40d3d4617d444348d1bad7cf780ec2f
68 Ne3d4569519964e69875f2aa13dc1d2da schema:familyName Lange
69 schema:givenName Otto
70 rdf:type schema:Person
71 Ne40d3d4617d444348d1bad7cf780ec2f rdf:first Ne3d4569519964e69875f2aa13dc1d2da
72 rdf:rest rdf:nil
73 Ne64f5eda634646bf9cfb1a0f80807927 rdf:first sg:person.012144130473.77
74 rdf:rest rdf:nil
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)


...