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


Ontology type: schema:Chapter     


Chapter Info

DATE

2010

AUTHORS

Bang Ye Wu

ABSTRACT

Given an undirected graph G = (V,E) with positive edge weights and two vertices s and t, the next-to-shortest path problem is to find an st-path which length is minimum among all st-paths of lengths strictly larger than the shortest path length. In this paper we give an O(|V|log|V| + |E|) time algorithm for this problem, which improves the previous result of O(|V|2) time for sparse graphs. More... »

PAGES

219-227

Book

TITLE

Combinatorial Optimization and Applications

ISBN

978-3-642-17460-5
978-3-642-17461-2

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-17461-2_18

DOI

http://dx.doi.org/10.1007/978-3-642-17461-2_18

DIMENSIONS

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


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 R.O.C.", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "National Chung Cheng University, 621, ChiaYi, Taiwan R.O.C."
          ], 
          "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"
      }
    ], 
    "datePublished": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "Given an undirected graph G\u2009=\u2009(V,E) with positive edge weights and two vertices s and t, the next-to-shortest path problem is to find an st-path which length is minimum among all st-paths of lengths strictly larger than the shortest path length. In this paper we give an O(|V|log|V|\u2009+\u2009|E|) time algorithm for this problem, which improves the previous result of O(|V|2) time for sparse graphs.", 
    "editor": [
      {
        "familyName": "Wu", 
        "givenName": "Weili", 
        "type": "Person"
      }, 
      {
        "familyName": "Daescu", 
        "givenName": "Ovidiu", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-17461-2_18", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-17460-5", 
        "978-3-642-17461-2"
      ], 
      "name": "Combinatorial Optimization and Applications", 
      "type": "Book"
    }, 
    "keywords": [
      "weight", 
      "length", 
      "shortest path length", 
      "previous results", 
      "results", 
      "time", 
      "problem", 
      "path length", 
      "Next", 
      "paper", 
      "algorithm", 
      "graph G", 
      "graph", 
      "undirected graph G", 
      "positive edge weights", 
      "edge weights", 
      "vertices s", 
      "shortest path problem", 
      "path problem", 
      "time algorithm", 
      "sparse graphs", 
      "efficient algorithm", 
      "Shortest Path Problem"
    ], 
    "name": "A Simpler and More Efficient Algorithm for the Next-to-Shortest Path Problem", 
    "pagination": "219-227", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1047601170"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-17461-2_18"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-17461-2_18", 
      "https://app.dimensions.ai/details/publication/pub.1047601170"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:27", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_71.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-17461-2_18"
  }
]
 

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/978-3-642-17461-2_18'

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/978-3-642-17461-2_18'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-17461-2_18'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-17461-2_18'


 

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

88 TRIPLES      23 PREDICATES      49 URIs      42 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-17461-2_18 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N46082578e2c14e52bcf04b49932269d2
4 schema:datePublished 2010
5 schema:datePublishedReg 2010-01-01
6 schema:description Given an undirected graph G = (V,E) with positive edge weights and two vertices s and t, the next-to-shortest path problem is to find an st-path which length is minimum among all st-paths of lengths strictly larger than the shortest path length. In this paper we give an O(|V|log|V| + |E|) time algorithm for this problem, which improves the previous result of O(|V|2) time for sparse graphs.
7 schema:editor Nfb857076c4044c9fb205f3f2beed5719
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N99a202b826474461a2d089cc1c5c93ef
12 schema:keywords Next
13 Shortest Path Problem
14 algorithm
15 edge weights
16 efficient algorithm
17 graph
18 graph G
19 length
20 paper
21 path length
22 path problem
23 positive edge weights
24 previous results
25 problem
26 results
27 shortest path length
28 shortest path problem
29 sparse graphs
30 time
31 time algorithm
32 undirected graph G
33 vertices s
34 weight
35 schema:name A Simpler and More Efficient Algorithm for the Next-to-Shortest Path Problem
36 schema:pagination 219-227
37 schema:productId N2fa8f0f6318a49c1af9ff63da304ca56
38 Nfb8146163eb240edb51f04ee9c9a4457
39 schema:publisher N9098b0c8f3004c118046f175b66b1274
40 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047601170
41 https://doi.org/10.1007/978-3-642-17461-2_18
42 schema:sdDatePublished 2022-01-01T19:27
43 schema:sdLicense https://scigraph.springernature.com/explorer/license/
44 schema:sdPublisher Nde0366f663414cb5b05712a323cab285
45 schema:url https://doi.org/10.1007/978-3-642-17461-2_18
46 sgo:license sg:explorer/license/
47 sgo:sdDataset chapters
48 rdf:type schema:Chapter
49 N06d7b75bd9e840f7807eb75b49ca7272 rdf:first N7ee4f2e4b6674af18e30ed5353ed085b
50 rdf:rest rdf:nil
51 N2fa8f0f6318a49c1af9ff63da304ca56 schema:name doi
52 schema:value 10.1007/978-3-642-17461-2_18
53 rdf:type schema:PropertyValue
54 N46082578e2c14e52bcf04b49932269d2 rdf:first sg:person.013045767237.23
55 rdf:rest rdf:nil
56 N7ee4f2e4b6674af18e30ed5353ed085b schema:familyName Daescu
57 schema:givenName Ovidiu
58 rdf:type schema:Person
59 N9098b0c8f3004c118046f175b66b1274 schema:name Springer Nature
60 rdf:type schema:Organisation
61 N99a202b826474461a2d089cc1c5c93ef schema:isbn 978-3-642-17460-5
62 978-3-642-17461-2
63 schema:name Combinatorial Optimization and Applications
64 rdf:type schema:Book
65 Nde0366f663414cb5b05712a323cab285 schema:name Springer Nature - SN SciGraph project
66 rdf:type schema:Organization
67 Nec3e4da1fd444a47bcf7541cc6c7bdff schema:familyName Wu
68 schema:givenName Weili
69 rdf:type schema:Person
70 Nfb8146163eb240edb51f04ee9c9a4457 schema:name dimensions_id
71 schema:value pub.1047601170
72 rdf:type schema:PropertyValue
73 Nfb857076c4044c9fb205f3f2beed5719 rdf:first Nec3e4da1fd444a47bcf7541cc6c7bdff
74 rdf:rest N06d7b75bd9e840f7807eb75b49ca7272
75 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
76 schema:name Information and Computing Sciences
77 rdf:type schema:DefinedTerm
78 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
79 schema:name Computation Theory and Mathematics
80 rdf:type schema:DefinedTerm
81 sg:person.013045767237.23 schema:affiliation grid-institutes:None
82 schema:familyName Wu
83 schema:givenName Bang Ye
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013045767237.23
85 rdf:type schema:Person
86 grid-institutes:None schema:alternateName National Chung Cheng University, 621, ChiaYi, Taiwan R.O.C.
87 schema:name National Chung Cheng University, 621, ChiaYi, Taiwan R.O.C.
88 rdf:type schema:Organization
 




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


...