Parallel algorithms for the single source shortest path problem View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1982-03

AUTHORS

P. Mateti, N. Deo

ABSTRACT

We present several parallel algorithms for the problem of finding shortest paths from a specified vertex (called the source) to all others in a weighted directed graph. The algorithms are for machines ranging from array processors, multipleinstruction multiple-data stream machines to a special network of processors. These algorithms have been designed by “parallelizing” two classic sequential algorithms — one due to Dijkstra (1959), the other due to Moore (1957). Our interest is not only in obtaining speeded-up parallel versions of the algorithms but also in exploring the design principles, the commonality of correctness proofs of the different versions, and the subjective complexity of explaining and understanding these versions. More... »

PAGES

31-49

References to SciGraph publications

  • 1959-12. A note on two problems in connexion with graphs in NUMERISCHE MATHEMATIK
  • Identifiers

    URI

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

    DOI

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

    DIMENSIONS

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


    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": "Case Western Reserve University", 
              "id": "https://www.grid.ac/institutes/grid.67105.35", 
              "name": [
                "Department of Computer Engineering and Science, Case Western Reserve University, 44106, Cleveland, OH, U.S.A."
              ], 
              "type": "Organization"
            }, 
            "familyName": "Mateti", 
            "givenName": "P.", 
            "id": "sg:person.013401416771.54", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013401416771.54"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Washington State University", 
              "id": "https://www.grid.ac/institutes/grid.30064.31", 
              "name": [
                "Computer Science Department, Washington State University, 99164, Pullman, WA, U.S.A."
              ], 
              "type": "Organization"
            }, 
            "familyName": "Deo", 
            "givenName": "N.", 
            "id": "sg:person.010274011142.47", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010274011142.47"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1145/360051.360224", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010101604"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/321765.321768", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013083968"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/360248.360251", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014038484"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/355900.355919", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024846798"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0196-6774(80)90004-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032472185"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/359138.359141", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038615532"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0065-2458(08)60033-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039527861"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01386390", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041716633", 
              "https://doi.org/10.1007/bf01386390"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-3975(81)90110-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052757172"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tse.1977.229904", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061787166"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tse.1981.230833", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061787433"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0207020", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841414"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1982-03", 
        "datePublishedReg": "1982-03-01", 
        "description": "We present several parallel algorithms for the problem of finding shortest paths from a specified vertex (called the source) to all others in a weighted directed graph. The algorithms are for machines ranging from array processors, multipleinstruction multiple-data stream machines to a special network of processors. These algorithms have been designed by \u201cparallelizing\u201d two classic sequential algorithms \u2014 one due to Dijkstra (1959), the other due to Moore (1957). Our interest is not only in obtaining speeded-up parallel versions of the algorithms but also in exploring the design principles, the commonality of correctness proofs of the different versions, and the subjective complexity of explaining and understanding these versions.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/bf02254849", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1356894", 
            "issn": [
              "1521-9615", 
              "1436-5057"
            ], 
            "name": "Computing", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "29"
          }
        ], 
        "name": "Parallel algorithms for the single source shortest path problem", 
        "pagination": "31-49", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "07d62eb86d7842262c45f116ba93df5e8865214bab094559017a22b336e7d89f"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf02254849"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1001645226"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf02254849", 
          "https://app.dimensions.ai/details/publication/pub.1001645226"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T12: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/0000000362_0000000362/records_87115_00000000.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007%2FBF02254849"
      }
    ]
     

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

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

    Turtle is a human-readable linked data format.

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

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

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


     

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

    108 TRIPLES      21 PREDICATES      39 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf02254849 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N16fe5ad9d390498aba40dc6a827d2bbf
    4 schema:citation sg:pub.10.1007/bf01386390
    5 https://doi.org/10.1016/0196-6774(80)90004-8
    6 https://doi.org/10.1016/0304-3975(81)90110-9
    7 https://doi.org/10.1016/s0065-2458(08)60033-9
    8 https://doi.org/10.1109/tse.1977.229904
    9 https://doi.org/10.1109/tse.1981.230833
    10 https://doi.org/10.1137/0207020
    11 https://doi.org/10.1145/321765.321768
    12 https://doi.org/10.1145/355900.355919
    13 https://doi.org/10.1145/359138.359141
    14 https://doi.org/10.1145/360051.360224
    15 https://doi.org/10.1145/360248.360251
    16 schema:datePublished 1982-03
    17 schema:datePublishedReg 1982-03-01
    18 schema:description We present several parallel algorithms for the problem of finding shortest paths from a specified vertex (called the source) to all others in a weighted directed graph. The algorithms are for machines ranging from array processors, multipleinstruction multiple-data stream machines to a special network of processors. These algorithms have been designed by “parallelizing” two classic sequential algorithms — one due to Dijkstra (1959), the other due to Moore (1957). Our interest is not only in obtaining speeded-up parallel versions of the algorithms but also in exploring the design principles, the commonality of correctness proofs of the different versions, and the subjective complexity of explaining and understanding these versions.
    19 schema:genre research_article
    20 schema:inLanguage en
    21 schema:isAccessibleForFree false
    22 schema:isPartOf N2eac6b29620b44bbae396a9369f347bd
    23 Nadb84d238031456d96f7743cff4dd149
    24 sg:journal.1356894
    25 schema:name Parallel algorithms for the single source shortest path problem
    26 schema:pagination 31-49
    27 schema:productId N5dca69f46bdb49e1b3c6c6c274c448ca
    28 N6dd28a8a90324dd9acb8ec0e8a497c1a
    29 Ndf9a39457ef443caac25a6cc49e4ab8d
    30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001645226
    31 https://doi.org/10.1007/bf02254849
    32 schema:sdDatePublished 2019-04-11T12:26
    33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    34 schema:sdPublisher N675923cd6a7c40a0af56d501c137ac17
    35 schema:url http://link.springer.com/10.1007%2FBF02254849
    36 sgo:license sg:explorer/license/
    37 sgo:sdDataset articles
    38 rdf:type schema:ScholarlyArticle
    39 N16fe5ad9d390498aba40dc6a827d2bbf rdf:first sg:person.013401416771.54
    40 rdf:rest N72f09c15c62f4cefa5c937718ceeb2bb
    41 N2eac6b29620b44bbae396a9369f347bd schema:volumeNumber 29
    42 rdf:type schema:PublicationVolume
    43 N5dca69f46bdb49e1b3c6c6c274c448ca schema:name dimensions_id
    44 schema:value pub.1001645226
    45 rdf:type schema:PropertyValue
    46 N675923cd6a7c40a0af56d501c137ac17 schema:name Springer Nature - SN SciGraph project
    47 rdf:type schema:Organization
    48 N6dd28a8a90324dd9acb8ec0e8a497c1a schema:name readcube_id
    49 schema:value 07d62eb86d7842262c45f116ba93df5e8865214bab094559017a22b336e7d89f
    50 rdf:type schema:PropertyValue
    51 N72f09c15c62f4cefa5c937718ceeb2bb rdf:first sg:person.010274011142.47
    52 rdf:rest rdf:nil
    53 Nadb84d238031456d96f7743cff4dd149 schema:issueNumber 1
    54 rdf:type schema:PublicationIssue
    55 Ndf9a39457ef443caac25a6cc49e4ab8d schema:name doi
    56 schema:value 10.1007/bf02254849
    57 rdf:type schema:PropertyValue
    58 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    59 schema:name Information and Computing Sciences
    60 rdf:type schema:DefinedTerm
    61 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    62 schema:name Computation Theory and Mathematics
    63 rdf:type schema:DefinedTerm
    64 sg:journal.1356894 schema:issn 1436-5057
    65 1521-9615
    66 schema:name Computing
    67 rdf:type schema:Periodical
    68 sg:person.010274011142.47 schema:affiliation https://www.grid.ac/institutes/grid.30064.31
    69 schema:familyName Deo
    70 schema:givenName N.
    71 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010274011142.47
    72 rdf:type schema:Person
    73 sg:person.013401416771.54 schema:affiliation https://www.grid.ac/institutes/grid.67105.35
    74 schema:familyName Mateti
    75 schema:givenName P.
    76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013401416771.54
    77 rdf:type schema:Person
    78 sg:pub.10.1007/bf01386390 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041716633
    79 https://doi.org/10.1007/bf01386390
    80 rdf:type schema:CreativeWork
    81 https://doi.org/10.1016/0196-6774(80)90004-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032472185
    82 rdf:type schema:CreativeWork
    83 https://doi.org/10.1016/0304-3975(81)90110-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052757172
    84 rdf:type schema:CreativeWork
    85 https://doi.org/10.1016/s0065-2458(08)60033-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039527861
    86 rdf:type schema:CreativeWork
    87 https://doi.org/10.1109/tse.1977.229904 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061787166
    88 rdf:type schema:CreativeWork
    89 https://doi.org/10.1109/tse.1981.230833 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061787433
    90 rdf:type schema:CreativeWork
    91 https://doi.org/10.1137/0207020 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841414
    92 rdf:type schema:CreativeWork
    93 https://doi.org/10.1145/321765.321768 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013083968
    94 rdf:type schema:CreativeWork
    95 https://doi.org/10.1145/355900.355919 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024846798
    96 rdf:type schema:CreativeWork
    97 https://doi.org/10.1145/359138.359141 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038615532
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1145/360051.360224 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010101604
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1145/360248.360251 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014038484
    102 rdf:type schema:CreativeWork
    103 https://www.grid.ac/institutes/grid.30064.31 schema:alternateName Washington State University
    104 schema:name Computer Science Department, Washington State University, 99164, Pullman, WA, U.S.A.
    105 rdf:type schema:Organization
    106 https://www.grid.ac/institutes/grid.67105.35 schema:alternateName Case Western Reserve University
    107 schema:name Department of Computer Engineering and Science, Case Western Reserve University, 44106, Cleveland, OH, U.S.A.
    108 rdf:type schema:Organization
     




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


    ...