An efficient parallel algorithm for shortest paths in planar layered digraphs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1995-10

AUTHORS

S. Subramanian, R. Tamassia, J. S. Vitter

ABSTRACT

Computing shortest paths in a directed graph has received considerable attention in the sequential RAM model of computation. However, developing a polylog-time parallel algorithm that is close to the sequential optimal in terms of the total work done remains an elusive goal. We present a first step in this direction by giving efficient parallel algorithms for shortest paths in planar layered digraphs. We show that these graphs admit special kinds of separators calledone- way separators which allow the paths in the graph to cross it only once. We use these separators to give divide- and -conquer solutions to the problem of finding the shortest paths between any two vertices. We first give a simple algorithm that works in the CREW model and computes the shortest path between any two vertices in ann-node planar layered digraph in timeO(log2n) usingn/logn processors. We then use results of Aggarwal and Park [1] and Atallah [4] to improve the time bound toO(log2n) in the CREW model andO(logn log logn) in the CREW model. The processor bounds still remain asn/logn for the CREW model andn/log logn for the CRCW model. More... »

PAGES

322-339

References to SciGraph publications

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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": "Brown University", 
          "id": "https://www.grid.ac/institutes/grid.40263.33", 
          "name": [
            "Department of Computer Science, Brown University, 02912-1910, Providence, RI, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Subramanian", 
        "givenName": "S.", 
        "id": "sg:person.012762721036.23", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012762721036.23"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Brown University", 
          "id": "https://www.grid.ac/institutes/grid.40263.33", 
          "name": [
            "Department of Computer Science, Brown University, 02912-1910, Providence, RI, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tamassia", 
        "givenName": "R.", 
        "id": "sg:person.0674326220.33", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0674326220.33"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Duke University", 
          "id": "https://www.grid.ac/institutes/grid.26009.3d", 
          "name": [
            "Department of Computer Science, Duke University, 27708-0129, Durham, NC, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vitter", 
        "givenName": "J. S.", 
        "id": "sg:person.0613677314.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/28869.28874", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1002799108"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/100216.100255", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007070527"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0022-0000(86)90030-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009976731"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-52846-6_89", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018196765", 
          "https://doi.org/10.1007/3-540-52846-6_89"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/165231.165240", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027133305"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0022-0000(89)90013-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032392570"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/140901.141913", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036403388"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0040377", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036696831", 
          "https://doi.org/10.1007/bfb0040377"
        ], 
        "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": "sg:pub.10.1007/3-540-17218-1_65", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1042746255", 
          "https://doi.org/10.1007/3-540-17218-1_65"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01840401", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050631860", 
          "https://doi.org/10.1007/bf01840401"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0020-0190(91)90013-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052014647"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/qam/102435", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1059346713"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0209046", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841535"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0211023", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841639"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0216064", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062842010"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0219066", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062842249"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0220045", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062842305"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sfcs.1988.21966", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086228996"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sfcs.1987.3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086238128"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1995-10", 
    "datePublishedReg": "1995-10-01", 
    "description": "Computing shortest paths in a directed graph has received considerable attention in the sequential RAM model of computation. However, developing a polylog-time parallel algorithm that is close to the sequential optimal in terms of the total work done remains an elusive goal. We present a first step in this direction by giving efficient parallel algorithms for shortest paths in planar layered digraphs. We show that these graphs admit special kinds of separators calledone- way separators which allow the paths in the graph to cross it only once. We use these separators to give divide- and -conquer solutions to the problem of finding the shortest paths between any two vertices. We first give a simple algorithm that works in the CREW model and computes the shortest path between any two vertices in ann-node planar layered digraph in timeO(log2n) usingn/logn processors. We then use results of Aggarwal and Park [1] and Atallah [4] to improve the time bound toO(log2n) in the CREW model andO(logn log logn) in the CREW model. The processor bounds still remain asn/logn for the CREW model andn/log logn for the CRCW model.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf01294130", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "14"
      }
    ], 
    "name": "An efficient parallel algorithm for shortest paths in planar layered digraphs", 
    "pagination": "322-339", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "ba06132ac75c4eb301476fb109eff65d998ae4534304e1d5c3c05ae3b0263dc8"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01294130"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1039052175"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01294130", 
      "https://app.dimensions.ai/details/publication/pub.1039052175"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T13:28", 
    "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/0000000370_0000000370/records_46741_00000002.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/BF01294130"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

143 TRIPLES      21 PREDICATES      47 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01294130 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N70f9c8c761c6467293c937da66b98d01
4 schema:citation sg:pub.10.1007/3-540-17218-1_65
5 sg:pub.10.1007/3-540-52846-6_89
6 sg:pub.10.1007/bf01386390
7 sg:pub.10.1007/bf01840401
8 sg:pub.10.1007/bfb0040377
9 https://doi.org/10.1016/0020-0190(91)90013-8
10 https://doi.org/10.1016/0022-0000(86)90030-9
11 https://doi.org/10.1016/0022-0000(89)90013-5
12 https://doi.org/10.1090/qam/102435
13 https://doi.org/10.1109/sfcs.1987.3
14 https://doi.org/10.1109/sfcs.1988.21966
15 https://doi.org/10.1137/0209046
16 https://doi.org/10.1137/0211023
17 https://doi.org/10.1137/0216064
18 https://doi.org/10.1137/0219066
19 https://doi.org/10.1137/0220045
20 https://doi.org/10.1145/100216.100255
21 https://doi.org/10.1145/140901.141913
22 https://doi.org/10.1145/165231.165240
23 https://doi.org/10.1145/28869.28874
24 schema:datePublished 1995-10
25 schema:datePublishedReg 1995-10-01
26 schema:description Computing shortest paths in a directed graph has received considerable attention in the sequential RAM model of computation. However, developing a polylog-time parallel algorithm that is close to the sequential optimal in terms of the total work done remains an elusive goal. We present a first step in this direction by giving efficient parallel algorithms for shortest paths in planar layered digraphs. We show that these graphs admit special kinds of separators calledone- way separators which allow the paths in the graph to cross it only once. We use these separators to give divide- and -conquer solutions to the problem of finding the shortest paths between any two vertices. We first give a simple algorithm that works in the CREW model and computes the shortest path between any two vertices in ann-node planar layered digraph in timeO(log2n) usingn/logn processors. We then use results of Aggarwal and Park [1] and Atallah [4] to improve the time bound toO(log2n) in the CREW model andO(logn log logn) in the CREW model. The processor bounds still remain asn/logn for the CREW model andn/log logn for the CRCW model.
27 schema:genre research_article
28 schema:inLanguage en
29 schema:isAccessibleForFree false
30 schema:isPartOf N49a20aae806c410cbb79ffd840e63b68
31 Ndd2b6e341023405294648e3b0ac413f2
32 sg:journal.1047644
33 schema:name An efficient parallel algorithm for shortest paths in planar layered digraphs
34 schema:pagination 322-339
35 schema:productId N322813f755604da5a1bfa7f5b7928d3d
36 N7ff21cfc048145909fc3c1f5a209c406
37 Nf3768b54f4c64203bb5933d96c27e553
38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039052175
39 https://doi.org/10.1007/bf01294130
40 schema:sdDatePublished 2019-04-11T13:28
41 schema:sdLicense https://scigraph.springernature.com/explorer/license/
42 schema:sdPublisher N6cb50784afec4449a82f9655637f23af
43 schema:url http://link.springer.com/10.1007/BF01294130
44 sgo:license sg:explorer/license/
45 sgo:sdDataset articles
46 rdf:type schema:ScholarlyArticle
47 N322813f755604da5a1bfa7f5b7928d3d schema:name doi
48 schema:value 10.1007/bf01294130
49 rdf:type schema:PropertyValue
50 N49a20aae806c410cbb79ffd840e63b68 schema:issueNumber 4
51 rdf:type schema:PublicationIssue
52 N6cb50784afec4449a82f9655637f23af schema:name Springer Nature - SN SciGraph project
53 rdf:type schema:Organization
54 N70f9c8c761c6467293c937da66b98d01 rdf:first sg:person.012762721036.23
55 rdf:rest Nb8c30a46fbeb447ebafd53380e0d7912
56 N7ff21cfc048145909fc3c1f5a209c406 schema:name readcube_id
57 schema:value ba06132ac75c4eb301476fb109eff65d998ae4534304e1d5c3c05ae3b0263dc8
58 rdf:type schema:PropertyValue
59 Nb8c30a46fbeb447ebafd53380e0d7912 rdf:first sg:person.0674326220.33
60 rdf:rest Nfbeb539b43f441dfb5f71708a2ee5863
61 Ndd2b6e341023405294648e3b0ac413f2 schema:volumeNumber 14
62 rdf:type schema:PublicationVolume
63 Nf3768b54f4c64203bb5933d96c27e553 schema:name dimensions_id
64 schema:value pub.1039052175
65 rdf:type schema:PropertyValue
66 Nfbeb539b43f441dfb5f71708a2ee5863 rdf:first sg:person.0613677314.28
67 rdf:rest rdf:nil
68 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
69 schema:name Information and Computing Sciences
70 rdf:type schema:DefinedTerm
71 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
72 schema:name Computation Theory and Mathematics
73 rdf:type schema:DefinedTerm
74 sg:journal.1047644 schema:issn 0178-4617
75 1432-0541
76 schema:name Algorithmica
77 rdf:type schema:Periodical
78 sg:person.012762721036.23 schema:affiliation https://www.grid.ac/institutes/grid.40263.33
79 schema:familyName Subramanian
80 schema:givenName S.
81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012762721036.23
82 rdf:type schema:Person
83 sg:person.0613677314.28 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
84 schema:familyName Vitter
85 schema:givenName J. S.
86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28
87 rdf:type schema:Person
88 sg:person.0674326220.33 schema:affiliation https://www.grid.ac/institutes/grid.40263.33
89 schema:familyName Tamassia
90 schema:givenName R.
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0674326220.33
92 rdf:type schema:Person
93 sg:pub.10.1007/3-540-17218-1_65 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042746255
94 https://doi.org/10.1007/3-540-17218-1_65
95 rdf:type schema:CreativeWork
96 sg:pub.10.1007/3-540-52846-6_89 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018196765
97 https://doi.org/10.1007/3-540-52846-6_89
98 rdf:type schema:CreativeWork
99 sg:pub.10.1007/bf01386390 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041716633
100 https://doi.org/10.1007/bf01386390
101 rdf:type schema:CreativeWork
102 sg:pub.10.1007/bf01840401 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050631860
103 https://doi.org/10.1007/bf01840401
104 rdf:type schema:CreativeWork
105 sg:pub.10.1007/bfb0040377 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036696831
106 https://doi.org/10.1007/bfb0040377
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1016/0020-0190(91)90013-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052014647
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1016/0022-0000(86)90030-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009976731
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1016/0022-0000(89)90013-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032392570
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1090/qam/102435 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059346713
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1109/sfcs.1987.3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086238128
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1109/sfcs.1988.21966 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086228996
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1137/0209046 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841535
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1137/0211023 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841639
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1137/0216064 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842010
125 rdf:type schema:CreativeWork
126 https://doi.org/10.1137/0219066 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842249
127 rdf:type schema:CreativeWork
128 https://doi.org/10.1137/0220045 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842305
129 rdf:type schema:CreativeWork
130 https://doi.org/10.1145/100216.100255 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007070527
131 rdf:type schema:CreativeWork
132 https://doi.org/10.1145/140901.141913 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036403388
133 rdf:type schema:CreativeWork
134 https://doi.org/10.1145/165231.165240 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027133305
135 rdf:type schema:CreativeWork
136 https://doi.org/10.1145/28869.28874 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002799108
137 rdf:type schema:CreativeWork
138 https://www.grid.ac/institutes/grid.26009.3d schema:alternateName Duke University
139 schema:name Department of Computer Science, Duke University, 27708-0129, Durham, NC, USA
140 rdf:type schema:Organization
141 https://www.grid.ac/institutes/grid.40263.33 schema:alternateName Brown University
142 schema:name Department of Computer Science, Brown University, 02912-1910, Providence, RI, USA
143 rdf:type schema:Organization
 




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


...