A Simpler and More Efficient Algorithm for the Next-to-Shortest Path Problem View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2011-12-02

AUTHORS

Bang Ye Wu

ABSTRACT

Given an undirected graph G=(V,E) with positive edge lengths and two vertices s and t, the next-to-shortest path problem is to find an st-path which length is minimum amongst all st-paths strictly longer than the shortest path length. In this paper we show that the problem can be solved in linear time if the distances from s and t to all other vertices are given. Particularly our new algorithm runs in O(|V|log|V|+|E|) time for general graphs, which improves the previous result of O(|V|2) time and takes only linear time for unweighted graphs, planar graphs, and graphs with positive integer edge lengths. More... »

PAGES

467-479

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-011-9601-7

DOI

http://dx.doi.org/10.1007/s00453-011-9601-7

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "National Chung Cheng University, 621, ChiaYi, Taiwan, ROC", 
          "id": "http://www.grid.ac/institutes/grid.412047.4", 
          "name": [
            "National Chung Cheng University, 621, ChiaYi, Taiwan, ROC"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wu", 
        "givenName": "Bang Ye", 
        "id": "sg:person.013045767237.23", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/s12190-008-0218-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052174902", 
          "https://doi.org/10.1007/s12190-008-0218-1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-010-9402-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007423545", 
          "https://doi.org/10.1007/s00453-010-9402-4"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2011-12-02", 
    "datePublishedReg": "2011-12-02", 
    "description": "Given an undirected graph G=(V,E) with positive edge lengths and two vertices s and t, the next-to-shortest path problem is to find an st-path which length is minimum amongst all st-paths strictly longer than the shortest path length. In this paper we show that the problem can be solved in linear time if the distances from s and t to all other vertices are given. Particularly our new algorithm runs in O(|V|log|V|+|E|) time for general graphs, which improves the previous result of O(|V|2) time and takes only linear time for unweighted graphs, planar graphs, and graphs with positive integer edge lengths.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00453-011-9601-7", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "65"
      }
    ], 
    "keywords": [
      "shortest path problem", 
      "path problem", 
      "linear time", 
      "new algorithm runs", 
      "Shortest Path Problem", 
      "undirected graph", 
      "graph", 
      "edge length", 
      "vertices s", 
      "problem", 
      "shortest path length", 
      "path length", 
      "vertices", 
      "algorithm runs", 
      "general graphs", 
      "previous results", 
      "unweighted graphs", 
      "planar graphs", 
      "efficient algorithm", 
      "algorithm", 
      "length", 
      "time", 
      "distance", 
      "run", 
      "results", 
      "Next", 
      "positive edge lengths", 
      "st-paths", 
      "paper", 
      "positive integer edge lengths", 
      "integer edge lengths"
    ], 
    "name": "A Simpler and More Efficient Algorithm for the Next-to-Shortest Path Problem", 
    "pagination": "467-479", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1022903426"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00453-011-9601-7"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00453-011-9601-7", 
      "https://app.dimensions.ai/details/publication/pub.1022903426"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2021-12-01T19:26", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/article/article_542.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00453-011-9601-7"
  }
]
 

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/s00453-011-9601-7'

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/s00453-011-9601-7'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-011-9601-7'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-011-9601-7'


 

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

97 TRIPLES      22 PREDICATES      58 URIs      48 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00453-011-9601-7 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N44c9f6eba89041fa982b678b4e07a41c
4 schema:citation sg:pub.10.1007/s00453-010-9402-4
5 sg:pub.10.1007/s12190-008-0218-1
6 schema:datePublished 2011-12-02
7 schema:datePublishedReg 2011-12-02
8 schema:description Given an undirected graph G=(V,E) with positive edge lengths and two vertices s and t, the next-to-shortest path problem is to find an st-path which length is minimum amongst all st-paths strictly longer than the shortest path length. In this paper we show that the problem can be solved in linear time if the distances from s and t to all other vertices are given. Particularly our new algorithm runs in O(|V|log|V|+|E|) time for general graphs, which improves the previous result of O(|V|2) time and takes only linear time for unweighted graphs, planar graphs, and graphs with positive integer edge lengths.
9 schema:genre article
10 schema:inLanguage en
11 schema:isAccessibleForFree true
12 schema:isPartOf Nb8c9305a0f5a4f258ad603c8a1624529
13 Nd38ec64146424a93b902a4afafcaa0eb
14 sg:journal.1047644
15 schema:keywords Next
16 Shortest Path Problem
17 algorithm
18 algorithm runs
19 distance
20 edge length
21 efficient algorithm
22 general graphs
23 graph
24 integer edge lengths
25 length
26 linear time
27 new algorithm runs
28 paper
29 path length
30 path problem
31 planar graphs
32 positive edge lengths
33 positive integer edge lengths
34 previous results
35 problem
36 results
37 run
38 shortest path length
39 shortest path problem
40 st-paths
41 time
42 undirected graph
43 unweighted graphs
44 vertices
45 vertices s
46 schema:name A Simpler and More Efficient Algorithm for the Next-to-Shortest Path Problem
47 schema:pagination 467-479
48 schema:productId N44d9939dfa6c4098b5799a3f8e96046b
49 Na06bb4400a8a435bac64325f12bb92d3
50 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022903426
51 https://doi.org/10.1007/s00453-011-9601-7
52 schema:sdDatePublished 2021-12-01T19:26
53 schema:sdLicense https://scigraph.springernature.com/explorer/license/
54 schema:sdPublisher Ned7572cd9ad04ca088da07584367bf15
55 schema:url https://doi.org/10.1007/s00453-011-9601-7
56 sgo:license sg:explorer/license/
57 sgo:sdDataset articles
58 rdf:type schema:ScholarlyArticle
59 N44c9f6eba89041fa982b678b4e07a41c rdf:first sg:person.013045767237.23
60 rdf:rest rdf:nil
61 N44d9939dfa6c4098b5799a3f8e96046b schema:name doi
62 schema:value 10.1007/s00453-011-9601-7
63 rdf:type schema:PropertyValue
64 Na06bb4400a8a435bac64325f12bb92d3 schema:name dimensions_id
65 schema:value pub.1022903426
66 rdf:type schema:PropertyValue
67 Nb8c9305a0f5a4f258ad603c8a1624529 schema:volumeNumber 65
68 rdf:type schema:PublicationVolume
69 Nd38ec64146424a93b902a4afafcaa0eb schema:issueNumber 2
70 rdf:type schema:PublicationIssue
71 Ned7572cd9ad04ca088da07584367bf15 schema:name Springer Nature - SN SciGraph project
72 rdf:type schema:Organization
73 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
74 schema:name Information and Computing Sciences
75 rdf:type schema:DefinedTerm
76 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
77 schema:name Computation Theory and Mathematics
78 rdf:type schema:DefinedTerm
79 sg:journal.1047644 schema:issn 0178-4617
80 1432-0541
81 schema:name Algorithmica
82 schema:publisher Springer Nature
83 rdf:type schema:Periodical
84 sg:person.013045767237.23 schema:affiliation grid-institutes:grid.412047.4
85 schema:familyName Wu
86 schema:givenName Bang Ye
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23
88 rdf:type schema:Person
89 sg:pub.10.1007/s00453-010-9402-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007423545
90 https://doi.org/10.1007/s00453-010-9402-4
91 rdf:type schema:CreativeWork
92 sg:pub.10.1007/s12190-008-0218-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052174902
93 https://doi.org/10.1007/s12190-008-0218-1
94 rdf:type schema:CreativeWork
95 grid-institutes:grid.412047.4 schema:alternateName National Chung Cheng University, 621, ChiaYi, Taiwan, ROC
96 schema:name National Chung Cheng University, 621, ChiaYi, Taiwan, ROC
97 rdf:type schema:Organization
 




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


...